Advertisement
Guest User

Untitled

a guest
Jul 30th, 2017
194
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <set>
  3. #include <map>
  4. #include <utility>
  5. #include <vector>
  6. #include <cassert>
  7. #include <algorithm>
  8. #include <string>
  9. #include <iostream>
  10. using namespace std;
  11.  
  12. #define mp make_pair
  13. #define pb push_back
  14. #define sz(a) int((a).size())
  15. #define forn(i, n) for (int i=0; i<(n); ++i)
  16.  
  17. typedef pair<int,int> pii;
  18. typedef long long ll;
  19. typedef long double ld;
  20.  
  21. const int maxn = 712;
  22. const ld eps = 1e-9;
  23. const ld pi = acos(-1.0);
  24.  
  25. ll x[maxn], y[maxn];
  26. vector<int> g[maxn];
  27. vector<int> gt[maxn];
  28. int a[maxn][3];
  29. int n;
  30.  
  31.  
  32.  
  33. bool intersect(int i1, int j1, int i2, int j2)
  34. {
  35.   ll A1 = y[j1] - y[i1],
  36.      B1 = x[i1] - x[j1],
  37.      C1 = -x[i1]*A1 - y[i1]*B1,
  38.      A2 = y[j2] - y[i2],
  39.      B2 = x[i2] - x[j2],
  40.      C2 = -x[i2]*A2 - y[i2]*B2;
  41.  
  42.   ll p1 = A1*x[i2] + B1*y[i2] + C1,
  43.      p2 = A1*x[j2] + B1*y[j2] + C1,
  44.      p3 = A2*x[i1] + B2*y[i1] + C2,
  45.      p4 = A2*x[j1] + B2*y[j1] + C2;
  46.  
  47.   if ( ( p1 < 0 && p2 < 0 ) || ( p1 > 0 && p2 > 0 ) ) return false;
  48.   if ( ( p3 < 0 && p4 < 0 ) || ( p3 > 0 && p4 > 0 ) ) return false;
  49.  
  50.   return true;
  51. }
  52.  
  53. ld dist(int i, int j)
  54. {
  55.   ld res = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
  56.   return sqrt(res);
  57. }
  58.  
  59. bool t[maxn][3][maxn][3];
  60. vector<int> bad[maxn];
  61.  
  62. inline void add(int x, int y)
  63. {
  64.   g[x].pb(y);
  65.   gt[y].pb(x);
  66. }
  67.  
  68. void dfs(int x)
  69. {
  70.   u[x] = 1;
  71.   forn (i, sz(g[x])) if (!u[g[x][i]]) dfs(g[x][i]);
  72.   order.pb(x);
  73. }
  74.  
  75. void dfst(int x, int cc)
  76. {
  77.   c[x] = cc;
  78.   forn (i, sz(gt[x])) if (c[gt[x][i]] == -1) dfst(gt[x][i], cc);
  79. }
  80.  
  81. inline int neg(int x)
  82. {
  83.   if (x < n) return x+n;
  84.   return x-n;
  85. }
  86.  
  87. int ans[maxn];
  88. vector<int> vv[maxn];
  89.  
  90. bool build(ld A)
  91. {
  92.   forn (i, n) bad[i].clear();
  93.  
  94.   forn (i, n)
  95.   {
  96.     forn (j, 3)
  97.     {
  98.       int q = (j+1)%3, p = (j+2)%3;
  99.       ld t = (x[q]-x[i])*(x[p]-x[i]) + (y[q]-y[i])*(y[p]-y[i]);
  100.       t /= dist(i, q);
  101.       t /= dist(i, p);
  102.       ld ang = acos(t);
  103.       if (ang < (pi-A)+eps)
  104.       {
  105.         bad[i].pb(j);
  106.       }
  107.     }    
  108.   }
  109.   forn (i, n) if (sz(bad[i]) == 3)
  110.   {
  111.     return false;
  112.   }
  113.  
  114.   forn (i, n) forn (k, sz(bad[i])) forn (j, n) forn (l, sz(bad[j]))
  115.   if (t[i][bad[i][k]][j][bad[j][l]])
  116.   {
  117.     return false;
  118.   }
  119.   forn (i, n) vv[i].clear();
  120.   forn (i, n) forn (j, 3) if (j != bad[i][0]) vv[i].pb(j);
  121.  
  122.   return true;
  123.  
  124. }
  125.  
  126. bool solve(ld ang)
  127. {
  128.  
  129.   if (!build(ang)) return false;
  130.  
  131.   forn (i, n+n) g[i].clear(), gt[i].clear();
  132.   forn (i, n+n) u[i] = 0, c[i] = -1;
  133.   order.clear();
  134.  
  135.   forn (i, n) if (sz(bad[i]) == 2)
  136.   {
  137.     if (vv[i][0] == bad[i][1])
  138.       add(neg(i), i);
  139.     else
  140.       add(i, neg(i));
  141.   }
  142.  
  143.   forn (i, n) forn (k, 2) forn (j, n) forn (l, 2)
  144.     if (t[i][vv[i][k]][j][vv[j][l]])
  145.     {
  146.       add(i+n*k, neg(j+n*l));
  147.       add(j+n*l, neg(i+n*k));
  148.     }
  149.   forn (i, n) forn (j, n) forn (l, 2)
  150.    if (t[i][bad[i][0]][j][vv[j][l]])
  151.    {
  152.      add(j+n*l, neg(j+n*l));
  153.    }                        
  154.  
  155.  
  156.  
  157.   forn (i, n+n) if (!u[i]) dfs(i);
  158.   int cc = 0;
  159.   forn (i, n+n) if (c[order[n+n-i-1]]==-1) dfst(order[n+n+-i-1], cc++);
  160.   forn (i, n) if (c[i] == c[neg(i)]) return false;
  161.   forn (i, n) if (c[i] < c[neg(i)]) ans[i] = 0; else ans[i] = 1;
  162.   return true;
  163. }
  164.  
  165. int main()
  166. {
  167.   freopen("f.in", "r", stdin);
  168.   freopen("f.out", "w", stdout);
  169.  
  170.   scanf("%d", &n);
  171.   forn (i, n)
  172.   {
  173.     int xx; yy; scanf("%d %d", &xx, &yy);
  174.     x[i] = xx, y[i] = yy;
  175.     forn (j, 3) scanf("%d", &a[i][j]);  
  176.   }
  177.  
  178.   forn (i, n) forn (j, n) forn (k, 3) forn (l, 3)
  179.   {
  180.     int i1 = i, j1 = a[i][k]; if (i1 > j1) swap(i1, j1);
  181.     int i2 = j, j2 = a[j][l]; if (i2 > j2) swap(i2, j2);
  182.     if (i1==i2 || j1==j2 || i1==j2 || i2==j1) continue;
  183.     t[i][k][j][l] = intersect(i1, j1, i2, j2);
  184.   }
  185.  
  186.  
  187.  
  188.   ld l = 0, r = pi/3-eps;
  189.   forn (it, 100)
  190.   {
  191.     ld mid = 0.5*(l+r);
  192.     if (solve(mid)) r = mid; else l = mid;
  193.   }
  194.  
  195.   if (solve(l))
  196.   {
  197.    
  198.   }
  199.   else if (solve(r))
  200.   {
  201.   }
  202.   else
  203.   {
  204.     puts("Minister's life is short :(");
  205.   }
  206.  
  207.  
  208.  
  209.   return 0;
  210. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement