Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <set>
- #include <map>
- #include <utility>
- #include <vector>
- #include <cassert>
- #include <algorithm>
- #include <string>
- #include <iostream>
- using namespace std;
- #define mp make_pair
- #define pb push_back
- #define sz(a) int((a).size())
- #define forn(i, n) for (int i=0; i<(n); ++i)
- typedef pair<int,int> pii;
- typedef long long ll;
- typedef long double ld;
- const int maxn = 712;
- const ld eps = 1e-9;
- const ld pi = acos(-1.0);
- ll x[maxn], y[maxn];
- vector<int> g[maxn];
- vector<int> gt[maxn];
- int a[maxn][3];
- int n;
- bool intersect(int i1, int j1, int i2, int j2)
- {
- ll A1 = y[j1] - y[i1],
- B1 = x[i1] - x[j1],
- C1 = -x[i1]*A1 - y[i1]*B1,
- A2 = y[j2] - y[i2],
- B2 = x[i2] - x[j2],
- C2 = -x[i2]*A2 - y[i2]*B2;
- ll p1 = A1*x[i2] + B1*y[i2] + C1,
- p2 = A1*x[j2] + B1*y[j2] + C1,
- p3 = A2*x[i1] + B2*y[i1] + C2,
- p4 = A2*x[j1] + B2*y[j1] + C2;
- if ( ( p1 < 0 && p2 < 0 ) || ( p1 > 0 && p2 > 0 ) ) return false;
- if ( ( p3 < 0 && p4 < 0 ) || ( p3 > 0 && p4 > 0 ) ) return false;
- return true;
- }
- ld dist(int i, int j)
- {
- ld res = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
- return sqrt(res);
- }
- bool t[maxn][3][maxn][3];
- vector<int> bad[maxn];
- inline void add(int x, int y)
- {
- g[x].pb(y);
- gt[y].pb(x);
- }
- void dfs(int x)
- {
- u[x] = 1;
- forn (i, sz(g[x])) if (!u[g[x][i]]) dfs(g[x][i]);
- order.pb(x);
- }
- void dfst(int x, int cc)
- {
- c[x] = cc;
- forn (i, sz(gt[x])) if (c[gt[x][i]] == -1) dfst(gt[x][i], cc);
- }
- inline int neg(int x)
- {
- if (x < n) return x+n;
- return x-n;
- }
- int ans[maxn];
- vector<int> vv[maxn];
- bool build(ld A)
- {
- forn (i, n) bad[i].clear();
- forn (i, n)
- {
- forn (j, 3)
- {
- int q = (j+1)%3, p = (j+2)%3;
- ld t = (x[q]-x[i])*(x[p]-x[i]) + (y[q]-y[i])*(y[p]-y[i]);
- t /= dist(i, q);
- t /= dist(i, p);
- ld ang = acos(t);
- if (ang < (pi-A)+eps)
- {
- bad[i].pb(j);
- }
- }
- }
- forn (i, n) if (sz(bad[i]) == 3)
- {
- return false;
- }
- forn (i, n) forn (k, sz(bad[i])) forn (j, n) forn (l, sz(bad[j]))
- if (t[i][bad[i][k]][j][bad[j][l]])
- {
- return false;
- }
- forn (i, n) vv[i].clear();
- forn (i, n) forn (j, 3) if (j != bad[i][0]) vv[i].pb(j);
- return true;
- }
- bool solve(ld ang)
- {
- if (!build(ang)) return false;
- forn (i, n+n) g[i].clear(), gt[i].clear();
- forn (i, n+n) u[i] = 0, c[i] = -1;
- order.clear();
- forn (i, n) if (sz(bad[i]) == 2)
- {
- if (vv[i][0] == bad[i][1])
- add(neg(i), i);
- else
- add(i, neg(i));
- }
- forn (i, n) forn (k, 2) forn (j, n) forn (l, 2)
- if (t[i][vv[i][k]][j][vv[j][l]])
- {
- add(i+n*k, neg(j+n*l));
- add(j+n*l, neg(i+n*k));
- }
- forn (i, n) forn (j, n) forn (l, 2)
- if (t[i][bad[i][0]][j][vv[j][l]])
- {
- add(j+n*l, neg(j+n*l));
- }
- forn (i, n+n) if (!u[i]) dfs(i);
- int cc = 0;
- forn (i, n+n) if (c[order[n+n-i-1]]==-1) dfst(order[n+n+-i-1], cc++);
- forn (i, n) if (c[i] == c[neg(i)]) return false;
- forn (i, n) if (c[i] < c[neg(i)]) ans[i] = 0; else ans[i] = 1;
- return true;
- }
- int main()
- {
- freopen("f.in", "r", stdin);
- freopen("f.out", "w", stdout);
- scanf("%d", &n);
- forn (i, n)
- {
- int xx; yy; scanf("%d %d", &xx, &yy);
- x[i] = xx, y[i] = yy;
- forn (j, 3) scanf("%d", &a[i][j]);
- }
- forn (i, n) forn (j, n) forn (k, 3) forn (l, 3)
- {
- int i1 = i, j1 = a[i][k]; if (i1 > j1) swap(i1, j1);
- int i2 = j, j2 = a[j][l]; if (i2 > j2) swap(i2, j2);
- if (i1==i2 || j1==j2 || i1==j2 || i2==j1) continue;
- t[i][k][j][l] = intersect(i1, j1, i2, j2);
- }
- ld l = 0, r = pi/3-eps;
- forn (it, 100)
- {
- ld mid = 0.5*(l+r);
- if (solve(mid)) r = mid; else l = mid;
- }
- if (solve(l))
- {
- }
- else if (solve(r))
- {
- }
- else
- {
- puts("Minister's life is short :(");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement