Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <map>
- using namespace std;
- struct point
- {
- int x, y;
- point(int x, int y)
- : x(x)
- , y(y)
- {}
- };
- struct triangle
- {
- triangle() {}
- triangle(int a, int b, int c) {
- pts[0] = a; pts[1] = b; pts[2] = c;}
- int & operator [] (size_t id) { return pts[id]; }
- int const & operator [] (size_t id) const { return pts[id]; }
- private:
- int pts[3];
- };
- const int N = 5000;
- int n;
- vector<point> points;
- vector<triangle> all_triangles;
- vector<triangle> small_triangles;
- vector<vector<int> > g;
- map<long long, int> betw;
- map<long long, int> tr_id;
- bool used[N];
- bool canCut[N];
- int x, y;
- long long curS, needS;
- vector<bool> used_tr;
- int divide;
- double last_point_x;
- double last_point_y;
- vector<int> chain1;
- vector<int> chain2;
- int prev(int v) {
- v = (v - 1 + n) % n;
- while (used[v]) {
- v = (v - 1 + n) % n;
- }
- return v;
- }
- int next(int v) {
- v = (v + 1) % n;
- while (used[v]) {
- v = (v + 1) % n;
- }
- return v;
- }
- int orientation(point a, point b, point c) {
- long long l = (b.x - a.x) * 1LL * (c.y - a.y);
- long long r = (b.y - a.y) * 1LL * (c.x - a.x);
- long long res = l - r;
- return (res > 0 ? 1 : (res < 0 ? -1 : 0));
- }
- bool inside_triangle(triangle t, int pt) {
- return
- orientation(points[t[0]], points[t[1]], points[pt]) > 0 &&
- orientation(points[t[1]], points[t[2]], points[pt]) > 0 &&
- orientation(points[t[2]], points[t[0]], points[pt]) > 0;
- }
- void updCut(int v) {
- int pr = prev(v);
- int ne = next(v);
- if (orientation(points[pr], points[v], points[ne]) < 0) {
- canCut[v] = false;
- return;
- }
- bool ok = true;
- triangle tr(pr, v, ne);
- for (int i = 0; i < n; i++) {
- if (i == pr || i == ne || i == v || used[i])
- continue;
- if (inside_triangle(tr, i)) {
- ok = false;
- break;
- }
- }
- canCut[v] = ok;
- }
- void pri(triangle t) {
- for (int j = 0; j < 3; j++)
- cout << "(" << points[t[j]].x / 12. << ", " << points[t[j]].y / 12. << ", " << t[j] << ") ";
- cout << endl;
- }
- int get_betw(int p1, int p2) {
- if (p1 > p2)
- swap(p1, p2);
- long long hash= p1 * 1000000000LL + p2;
- int id = betw[hash];
- if (id == 0) {
- int x = (points[p1].x + points[p2].x) / 2;
- int y = (points[p1].y + points[p2].y) / 2;
- points.push_back(point(x, y));
- betw[hash] = points.size() - 1;
- return points.size() - 1;
- } else {
- return id;
- }
- }
- void addTr(int p1, int p2, int trId) {
- if (p1 > p2)
- swap(p1, p2);
- long long hash = 1000000000LL * p1 + p2;
- tr_id[hash] += 1 + trId;
- }
- int addTr_another(int p1, int p2, int trId) {
- if (p1 > p2)
- swap(p1, p2);
- long long hash = 1000000000LL * p1 + p2;
- int xx = tr_id[hash];
- if (xx == trId + 1)
- return -1;
- return xx - trId - 2;
- }
- bool in_tr(int v, int t) {
- return small_triangles[t][0] == v || small_triangles[t][1] == v || small_triangles[t][2] == v;
- }
- vector<int> same(int tr1, int tr2) {
- vector<int> res;
- for (int i = 0; i < 3; i++)
- if (in_tr(small_triangles[tr1][i], tr2))
- res.push_back(small_triangles[tr1][i]);
- return res;
- }
- void printChains() {
- /*
- cout << "chain1: ";
- for (int i = 0; i < chain1.size(); i++) {
- cout << chain1[i] << " ";
- }
- cout << endl;
- cout << "chain2: ";
- for (int i = 0; i < chain2.size(); i++) {
- cout << chain2[i] << " ";
- }
- cout << endl;
- */
- }
- void dfs(int v, int p) {
- //cout << "here " << v << endl;
- used_tr[v] = true;
- triangle t = small_triangles[v];
- point p1 = points[t[0]];
- point p2 = points[t[1]];
- point p3 = points[t[2]];
- long long addS = 0;
- addS += (p1.x - p2.x) * 1LL * (p1.y + p2.y) / 2;
- addS += (p2.x - p3.x) * 1LL * (p3.y + p2.y) / 2;
- addS += (p3.x - p1.x) * 1LL * (p1.y + p3.y) / 2;
- if (addS < 0)
- addS = -addS;
- //cout << "S = " << addS + curS << endl;
- if (addS + curS >= needS) {
- used_tr[v] = false;
- for (int i = 0; i < 3; i++) {
- int p11 = t[i];
- int p22 = t[(i + 1) % 3];
- int anoth = addTr_another(p11, p22, v);
- if (anoth != g[v][0] && anoth != g[v][1]) {
- divide = i;
- long long ostS = needS - curS;
- double divide_pr = ostS / (0.0 + addS);
- if (small_triangles[p][0] == p22 || small_triangles[p][1] == p22 || small_triangles[p][2] == p22)
- swap(p11, p22);
- point _p11 = points[p11];
- point _p22 = points[p22];
- last_point_x = _p11.x + (_p22.x - _p11.x) * divide_pr;
- last_point_y = _p11.y + (_p22.y - _p11.y) * divide_pr;
- //cout << "last is " << last_point_x / 2. << " " << last_point_y / 2. << endl;
- vector<int> sam = same(v, p);
- chain1.push_back(sam[0]);
- chain2.push_back(sam[1]);
- //cout << "last_points are " << points[sam[0]].x / 2 << " " << points[sam[0]].y / 2<< " " << points[sam[1]].x / 2 << " " << points[sam[1]].y / 2 << endl;
- break;
- }
- }
- return;
- }
- for (int i = 0; i < g[v].size(); i++) {
- int to = g[v][i];
- if (used_tr[to])
- continue;
- curS += addS;
- dfs(to, v);
- //cout << "out to " << v << " " << p << endl;
- if (p != -1) {
- int diff = t[0] + t[1] + t[2] - chain1[chain1.size() - 1] - chain2[chain2.size() - 1];
- // << "points are " << t[0] << " " << t[1] << " " << t[2] << "; chain ends with " << chain1[chain1.size() - 1] << " " << chain2[chain2.size() - 1] << endl;
- //cout << "add point " << points[diff].x / 2. << " " << points[diff].y / 2 << " to chain" << endl;
- if (in_tr(chain1[chain1.size() - 1], p))
- chain2.push_back(diff); else
- chain1.push_back(diff);
- //printChains();
- }
- return;
- }
- }
- void priv(int v) {
- printf("%d %d (point id = %d)\n", points[v].x , points[v].y, v);
- }
- void priv(double x, double y) {
- printf("%.18f %.18f", x , y);
- }
- void privReal(int v) {
- printf("%.18f %.18f\n", ((double) points[v].x) / 12.0, ((double)points[v].y) / 12.0);
- }
- void privReal(double x, double y) {
- printf("%.18f %.18f\n", x / 12.0, y / 12.0);
- }
- void out(int k) {
- triangle t = small_triangles[k];
- //cout << t[0] << " " << t[1] << " " << t[2] << endl;
- int diff = t[0] + t[1] + t[2] - chain1[chain1.size() - 1] - chain2[chain2.size() - 1];
- for (int i = 0; i < chain2.size(); i++) {
- if (chain2[i] == diff) {
- while (chain2.size() != i)
- chain2.pop_back();
- }
- }
- printf("%d\n", chain1.size() + chain2.size() + 2);
- //cout << "out figure!!!!!!!!!!!!!!!!!!" << endl;
- privReal(diff);
- for (int i = 0; i < chain1.size(); i++) {
- privReal(chain1[chain1.size() - 1 - i]);
- }
- privReal(last_point_x, last_point_y);
- for (int i = 0; i < chain2.size(); i++) {
- privReal(chain2[i]);
- }
- }
- int main() {
- freopen("kingdom.in", "r", stdin);
- freopen("kingdom.out", "w", stdout);
- scanf("%d", &n);
- for (int i = 0; i < n; i++) {
- scanf("%d%d", &x, &y);
- points.push_back(point(x * 12, y * 12));
- }
- for (int i = 0; i < n; i++)
- used[i] = false;
- for (int i = 0; i < n; i++) {
- updCut(i);
- }
- for (int it = 0; it < n - 2; it++) {
- int rem = -1;
- for (int i= 0; i < n; i++) {
- if (!used[i] && canCut[i]) {
- rem = i;
- }
- }
- if (rem == -1) {
- break;
- //cout << "fail, really" <<endl;
- //return 1;
- }
- int pr = prev(rem);
- int ne = next(rem);
- used[rem] = true;
- all_triangles.push_back(triangle(pr, rem, ne));
- updCut(pr);
- updCut(ne);
- }
- //cout << "----\n";
- //cout<<all_triangles.size() << endl;
- //for (int i = 0; i < all_triangles.size(); i++) {
- // triangle t = all_triangles[i];
- //pri(t);
- //}
- //cout << "----\n";
- for (int i = 0; i < all_triangles.size(); i++) {
- triangle t = all_triangles[i];
- int m1 = get_betw(t[0], t[1]);
- int m2 = get_betw(t[1], t[2]);
- int m3 = get_betw(t[2], t[0]);
- int xx = (points[t[0]].x + points[t[1]].x + points[t[2]].x) / 3;
- int yy = (points[t[0]].y + points[t[1]].y + points[t[2]].y) / 3;
- int med = points.size();
- points.push_back(point(xx, yy));
- small_triangles.push_back(triangle(t[0], m1, med));
- small_triangles.push_back(triangle(t[1], m1, med));
- small_triangles.push_back(triangle(t[1], m2, med));
- small_triangles.push_back(triangle(t[2], m2, med));
- small_triangles.push_back(triangle(t[2], m3, med));
- small_triangles.push_back(triangle(t[0], m3, med));
- }
- for (int i = 0; i < small_triangles.size(); i++) {
- vector<int> tmp;
- g.push_back(tmp);
- triangle t = small_triangles[i];
- addTr(t[0], t[1], i);
- addTr(t[1], t[2], i);
- addTr(t[2], t[0], i);
- }
- for (int i = 0; i < small_triangles.size(); i++) {
- triangle t = small_triangles[i];
- int getAn = addTr_another(t[0], t[1], i);
- if (getAn == -1) {
- int get_an2 = addTr_another(t[1], t[2], i);
- g[i].push_back(get_an2);
- } else {
- g[i].push_back(getAn);
- }
- int getAn3 = addTr_another(t[2], t[0], i);
- g[i].push_back(getAn3);
- }
- //cout << "!!!" << endl;
- //for (int i = 0; i < small_triangles.size(); i++) {
- // pri(small_triangles[i]);
- //}
- //for (int i = 0; i < small_triangles.size(); i++) {
- // for (int j = 0; j < g[i].size(); j++) {
- // cout << g[i][j] << " ";
- // }
- // cout << endl;
- // }
- //cout << "@@@\n";
- needS = 0;
- for (int i = 0; i < n; i++) {
- point p1 = points[i];
- point p2 = points[(i + 1) % n];
- needS += (p1.x - p2.x) * 1LL * (p1.y + p2.y) / 4;
- }
- //cout << needS << endl;
- for (int i = 0; i < small_triangles.size(); i++) {
- used_tr.push_back(false);
- }
- curS = 0;
- //cout << "ALL POINTS:::::::::::::::::" << endl;
- //for (int i= 0; i < points.size(); i++) {
- // cout << i << ": " << points[i].x / 2. << " " << points[i].y /2. << endl;
- //}
- //cout << "END ALL POINTS::::::::::::::::::" << endl;
- dfs(0, -1);
- //cout << "out from dfs" << endl;
- out(0);
- //cout << "end first part" << endl;
- chain1.clear();
- chain2.clear();
- curS = 0;
- dfs(g[0][1], -1);
- out(g[0][1]);
- }
Advertisement
Add Comment
Please, Sign In to add comment