qwerty787788

Untitled

May 1st, 2013
215
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.63 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. struct point
  9.    {
  10.       int x, y;
  11.  
  12.       point(int x, int y)
  13.          : x(x)
  14.          , y(y)
  15.       {}
  16.    };
  17.  
  18. struct triangle
  19.    {
  20.       triangle() {}
  21.       triangle(int a, int b, int c) {
  22.           pts[0] = a; pts[1] = b; pts[2] = c;}
  23.  
  24.       int &         operator [] (size_t id)       { return pts[id]; }
  25.       int const &   operator [] (size_t id) const { return pts[id]; }
  26.  
  27.    private:
  28.       int pts[3];
  29.    };
  30.  
  31.  
  32. const int N = 5000;
  33. int n;
  34. vector<point> points;
  35. vector<triangle> all_triangles;
  36. vector<triangle> small_triangles;
  37. vector<vector<int> > g;
  38. map<long long, int> betw;
  39. map<long long, int> tr_id;
  40. bool used[N];
  41. bool canCut[N];
  42. int x, y;
  43. long long curS, needS;
  44. vector<bool> used_tr;
  45. int divide;
  46. double last_point_x;
  47. double last_point_y;
  48. vector<int> chain1;
  49. vector<int> chain2;
  50.  
  51. int prev(int v) {
  52.     v = (v - 1 + n) % n;
  53.     while (used[v]) {
  54.         v = (v - 1 + n) % n;
  55.     }
  56.     return v;
  57. }
  58.  
  59. int next(int v) {
  60.     v = (v + 1) % n;
  61.     while (used[v]) {
  62.         v = (v + 1) % n;
  63.     }
  64.     return v;
  65. }
  66.  
  67. int orientation(point a, point b, point c) {
  68.     long long l = (b.x - a.x) * 1LL * (c.y - a.y);
  69.    long long r = (b.y - a.y) * 1LL * (c.x - a.x);
  70.    long long res = l - r;
  71.    return (res > 0 ? 1 : (res < 0 ? -1 : 0));
  72. }
  73.  
  74. bool inside_triangle(triangle t, int pt) {
  75.     return
  76.         orientation(points[t[0]], points[t[1]], points[pt]) > 0 &&
  77.         orientation(points[t[1]], points[t[2]], points[pt]) > 0 &&
  78.         orientation(points[t[2]], points[t[0]], points[pt]) > 0;
  79.  
  80. }
  81.  
  82. void updCut(int v) {
  83.     int pr = prev(v);
  84.     int ne = next(v);
  85.     if (orientation(points[pr], points[v], points[ne]) < 0) {
  86.         canCut[v] = false;
  87.         return;
  88.     }
  89.     bool ok = true;
  90.     triangle tr(pr, v, ne);
  91.     for (int i = 0; i < n; i++) {
  92.         if (i == pr || i == ne || i == v || used[i])
  93.             continue;
  94.         if (inside_triangle(tr, i)) {
  95.             ok = false;
  96.             break;
  97.         }
  98.     }
  99.     canCut[v] = ok;
  100. }
  101.  
  102. void pri(triangle t) {
  103.     for (int j = 0; j < 3; j++)
  104.         cout << "(" << points[t[j]].x / 12. << ", " << points[t[j]].y / 12. << ", " << t[j] << ") ";
  105.     cout << endl;
  106. }
  107.  
  108. int get_betw(int p1, int p2) {
  109.     if (p1 > p2)
  110.         swap(p1, p2);
  111.     long long hash= p1 * 1000000000LL + p2;
  112.     int id = betw[hash];
  113.     if (id == 0) {
  114.         int x = (points[p1].x + points[p2].x) / 2;
  115.         int y = (points[p1].y + points[p2].y) / 2;
  116.         points.push_back(point(x, y));
  117.         betw[hash] = points.size() - 1;
  118.         return points.size() - 1;
  119.     } else {
  120.         return id;
  121.     }
  122. }
  123.  
  124. void addTr(int p1, int p2, int trId) {
  125.     if (p1 > p2)
  126.         swap(p1, p2);
  127.     long long hash = 1000000000LL * p1 + p2;
  128.     tr_id[hash] += 1 + trId;
  129. }
  130.  
  131. int addTr_another(int p1, int p2, int trId) {
  132.     if (p1 > p2)
  133.         swap(p1, p2);
  134.     long long hash = 1000000000LL * p1 + p2;
  135.     int xx = tr_id[hash];
  136.     if (xx == trId + 1)
  137.         return -1;
  138.     return xx - trId - 2;
  139. }
  140.  
  141. bool in_tr(int v, int t) {
  142.     return small_triangles[t][0] == v || small_triangles[t][1] == v || small_triangles[t][2] == v;
  143. }
  144.  
  145. vector<int> same(int tr1, int tr2) {
  146.     vector<int> res;
  147.     for (int i = 0; i < 3; i++)
  148.         if (in_tr(small_triangles[tr1][i], tr2))
  149.             res.push_back(small_triangles[tr1][i]);
  150.     return res;
  151. }
  152.  
  153. void printChains() {
  154.     /*
  155.     cout << "chain1: ";
  156.     for (int i = 0; i < chain1.size(); i++) {
  157.         cout << chain1[i] << " ";
  158.     }
  159.     cout << endl;
  160.     cout << "chain2: ";
  161.     for (int i = 0; i < chain2.size(); i++) {
  162.         cout << chain2[i] << " ";
  163.     }
  164.     cout << endl;
  165.     */
  166. }
  167.  
  168. void dfs(int v, int p) {
  169.     //cout << "here " << v << endl;
  170.     used_tr[v] = true;
  171.     triangle t = small_triangles[v];
  172.     point p1 = points[t[0]];
  173.     point p2 = points[t[1]];
  174.     point p3 = points[t[2]];
  175.     long long addS = 0;
  176.     addS += (p1.x - p2.x) * 1LL * (p1.y + p2.y) / 2;
  177.     addS += (p2.x - p3.x) * 1LL * (p3.y + p2.y) / 2;
  178.     addS += (p3.x - p1.x) * 1LL * (p1.y + p3.y) / 2;
  179.     if (addS < 0)
  180.         addS = -addS;
  181.     //cout << "S = " << addS + curS << endl;
  182.     if (addS + curS >= needS) {
  183.         used_tr[v] = false;
  184.         for (int i = 0; i < 3; i++) {
  185.             int p11 = t[i];
  186.             int p22 = t[(i + 1) % 3];
  187.             int anoth = addTr_another(p11, p22, v);
  188.             if (anoth != g[v][0] && anoth != g[v][1]) {
  189.                 divide = i;
  190.                 long long ostS = needS - curS;
  191.                 double divide_pr = ostS / (0.0 + addS);
  192.                 if (small_triangles[p][0] == p22 || small_triangles[p][1] == p22 || small_triangles[p][2] == p22)
  193.                     swap(p11, p22);
  194.                 point _p11 = points[p11];
  195.                 point _p22 = points[p22];
  196.                 last_point_x = _p11.x + (_p22.x - _p11.x) * divide_pr;
  197.                 last_point_y = _p11.y + (_p22.y - _p11.y) * divide_pr;
  198.                 //cout << "last is " << last_point_x / 2. << " " << last_point_y / 2. << endl;
  199.                 vector<int> sam = same(v, p);
  200.                 chain1.push_back(sam[0]);
  201.                 chain2.push_back(sam[1]);
  202.                 //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;
  203.                 break;
  204.             }
  205.         }
  206.     return;
  207.     }
  208.     for (int i = 0; i < g[v].size(); i++) {
  209.         int to = g[v][i];
  210.         if (used_tr[to])
  211.             continue;
  212.         curS += addS;
  213.         dfs(to, v);
  214.         //cout << "out to " << v << " " << p << endl;
  215.         if (p != -1) {
  216.             int diff = t[0] + t[1] + t[2] - chain1[chain1.size() - 1] - chain2[chain2.size() - 1];
  217.             // << "points are " << t[0] << " " << t[1] << " " << t[2] << "; chain ends with " << chain1[chain1.size() - 1] << " " << chain2[chain2.size() - 1] << endl;
  218.             //cout << "add point " << points[diff].x / 2. << " " << points[diff].y / 2 << " to chain" << endl;
  219.             if (in_tr(chain1[chain1.size() - 1], p))
  220.                 chain2.push_back(diff); else
  221.                 chain1.push_back(diff);
  222.             //printChains();
  223.         }
  224.         return;
  225.     }
  226. }
  227.  
  228. void priv(int v) {
  229.     printf("%d %d (point id = %d)\n", points[v].x , points[v].y, v);
  230. }
  231.  
  232. void priv(double x, double y) {
  233.     printf("%.18f %.18f", x , y);
  234. }
  235.  
  236. void privReal(int v) {
  237.     printf("%.18f %.18f\n", ((double) points[v].x) / 12.0, ((double)points[v].y) / 12.0);
  238. }
  239.  
  240. void privReal(double x, double y) {
  241.     printf("%.18f %.18f\n", x / 12.0, y / 12.0);
  242. }
  243.  
  244. void out(int k) {
  245.     triangle t = small_triangles[k];
  246.     //cout << t[0] << " " << t[1] << " " << t[2] << endl;
  247.     int diff = t[0] + t[1] + t[2] - chain1[chain1.size() - 1] - chain2[chain2.size() - 1];
  248.     for (int i = 0; i < chain2.size(); i++) {
  249.         if (chain2[i] == diff) {
  250.             while (chain2.size() != i)
  251.                 chain2.pop_back();
  252.         }
  253.     }
  254.     printf("%d\n", chain1.size() + chain2.size() + 2);
  255.     //cout << "out figure!!!!!!!!!!!!!!!!!!" << endl;
  256.    
  257.     privReal(diff);
  258.     for (int i = 0; i < chain1.size(); i++) {
  259.         privReal(chain1[chain1.size() - 1 - i]);
  260.     }
  261.     privReal(last_point_x, last_point_y);
  262.     for (int i = 0; i < chain2.size(); i++) {
  263.         privReal(chain2[i]);
  264.     }
  265. }
  266.  
  267. int main() {
  268.     freopen("kingdom.in", "r", stdin);
  269.     freopen("kingdom.out", "w", stdout);
  270.     scanf("%d", &n);
  271.     for (int i  = 0; i < n; i++) {
  272.         scanf("%d%d", &x, &y);
  273.         points.push_back(point(x * 12, y * 12));
  274.     }
  275.     for (int i = 0; i < n; i++)
  276.         used[i] = false;
  277.     for (int i = 0; i < n; i++) {
  278.         updCut(i);
  279.     }
  280.     for (int it = 0; it < n - 2; it++) {
  281.         int rem = -1;
  282.         for (int i= 0; i < n; i++) {
  283.             if (!used[i] && canCut[i]) {
  284.                 rem = i;
  285.             }
  286.         }
  287.         if (rem == -1) {
  288.             cout << "fail, really" <<endl;
  289.             return 1;
  290.         }
  291.        
  292.         int pr = prev(rem);
  293.         int ne = next(rem);
  294.         used[rem] = true;
  295.         all_triangles.push_back(triangle(pr, rem, ne));
  296.         updCut(pr);
  297.         updCut(ne);
  298.     }
  299.     //cout << "----\n";
  300.     //cout<<all_triangles.size() << endl;
  301.     //for (int i = 0; i < all_triangles.size(); i++) {
  302.     //  triangle t = all_triangles[i];
  303.         //pri(t);
  304.     //}
  305.     //cout << "----\n";
  306.     for (int i = 0; i < all_triangles.size(); i++) {
  307.         triangle t = all_triangles[i];
  308.         int m1 = get_betw(t[0], t[1]);
  309.         int m2 = get_betw(t[1], t[2]);
  310.         int m3 = get_betw(t[2], t[0]);
  311.         int xx = (points[t[0]].x + points[t[1]].x + points[t[2]].x) / 3;
  312.         int yy = (points[t[0]].y + points[t[1]].y + points[t[2]].y) / 3;
  313.         int med = points.size();
  314.         points.push_back(point(xx, yy));
  315.         small_triangles.push_back(triangle(t[0], m1, med));
  316.         small_triangles.push_back(triangle(t[1], m1, med));
  317.         small_triangles.push_back(triangle(t[1], m2, med));
  318.         small_triangles.push_back(triangle(t[2], m2, med));
  319.         small_triangles.push_back(triangle(t[2], m3, med));
  320.         small_triangles.push_back(triangle(t[0], m3, med));
  321.     }
  322.     for (int i = 0; i < small_triangles.size(); i++) {
  323.         vector<int> tmp;
  324.         g.push_back(tmp);
  325.         triangle t = small_triangles[i];
  326.         addTr(t[0], t[1], i);
  327.         addTr(t[1], t[2], i);
  328.         addTr(t[2], t[0], i);
  329.     }
  330.     for (int i = 0; i < small_triangles.size(); i++) {
  331.         triangle t = small_triangles[i];
  332.         int getAn = addTr_another(t[0], t[1], i);
  333.         if (getAn == -1) {
  334.             int get_an2 = addTr_another(t[1], t[2], i);
  335.             g[i].push_back(get_an2);
  336.         } else {
  337.             g[i].push_back(getAn);
  338.         }
  339.         int getAn3 = addTr_another(t[2], t[0], i);
  340.         g[i].push_back(getAn3);
  341.     }
  342.     //cout << "!!!" << endl;
  343.     //for (int i = 0; i < small_triangles.size(); i++) {
  344.     //  pri(small_triangles[i]);
  345.     //}
  346.     //for (int i = 0; i < small_triangles.size(); i++) {
  347.     //  for (int j = 0; j < g[i].size(); j++) {
  348.     //      cout << g[i][j] << " ";
  349. //      }
  350.     //  cout << endl;
  351. //  }
  352.     //cout << "@@@\n";
  353.     needS = 0;
  354.     for (int i = 0; i < n; i++) {
  355.         point p1 = points[i];
  356.         point p2 = points[(i + 1) % n];
  357.         needS += (p1.x - p2.x) * 1LL * (p1.y + p2.y) / 4;
  358.     }
  359.     //cout << needS << endl;
  360.     for (int i = 0; i < small_triangles.size(); i++) {
  361.         used_tr.push_back(false);
  362.     }
  363.     curS = 0;
  364.     //cout << "ALL POINTS:::::::::::::::::" << endl;
  365.     //for (int i= 0; i < points.size(); i++) {
  366.     //  cout << i << ": " << points[i].x  / 2. << " " << points[i].y /2. << endl;
  367.     //}
  368.     //cout << "END ALL POINTS::::::::::::::::::" << endl;
  369.     dfs(0, -1);
  370.     //cout << "out from dfs" << endl;
  371.     out(0);
  372.     //cout << "end first part" << endl;
  373.     chain1.clear();
  374.     chain2.clear();
  375.     curS = 0;
  376.     dfs(g[0][1], -1);
  377.     out(g[0][1]);
  378. }
Advertisement
Add Comment
Please, Sign In to add comment