(I2
I121
I4
(dp0
Vsquares.%l
p1
(Vsquares.cpp
p2
S'#include <bits/stdc++.h>\r\n#define double_t double\r\n//#define fabs(a) ((a<0) ? -a : a)\r\n\r\nusing namespace std;\r\n\r\nconst double_t EPS = 0.000000001;\r\nconst double_t INF = 1e18;\r\n\r\nstruct point {\r\n    double_t x,y;\r\n    point(){}\r\n    point(double_t a, double_t b) {\r\n        x=a;\r\n        y=b;\r\n    }\r\n    bool operator <(const point &a) const {\r\n        if(x<a.x) return true;\r\n        if(x>a.x) return false;\r\n        return y<a.y;\r\n    }\r\n};\r\n\r\nint n;\r\npoint center[32],pt[32];\r\nvector <point> pts[32];\r\ndouble_t d;\r\nlong long up,down;\r\ndouble_t ans;\r\n\r\ntemplate <typename T>\r\nT fabs(T a) {\r\n    if(a<0) a*=(-1);\r\n    return a;\r\n}\r\n\r\nbool eq(double_t a, double_t b) {\r\n    return (fabs(a-b)<=EPS);\r\n}\r\n\r\ndouble_t s(point a, point b, point c) {\r\n    return ((a.x-b.x)*(a.y+b.y) + (b.x-c.x)*(b.y+c.y) + (c.x-a.x)*(c.y+a.y))/2;\r\n}\r\n\r\ndouble_t get_area(vector <point> p) {\r\n    if((int)(p.size())<=2) return 0;\r\n    double_t ans=0;\r\n    int i;\r\n    for(i=1;i<(int)(p.size())-1;i++) ans+=fabs(s(p[0],p[i],p[i+1]));\r\n    return ans;\r\n}\r\n\r\nbool is_it_in(vector <point> p, point a) {\r\n    double_t s1=get_area(p),s2=0;\r\n    int i;\r\n    if((int)(p.size())<=2) return false;\r\n    p.push_back(p[0]);\r\n    for(i=0;i<(int)(p.size())-1;i++) s2+=fabs(s(p[i],p[i+1],a));\r\n    //s2+=fabs(s(p[p.size()-1],p[0],a));\r\n    return (eq(s1,s2));\r\n}\r\n\r\nvoid get_equation(point p, point k, double_t &a, double_t &b, double_t &c) {\r\n    double_t x1=p.x,y1=p.y,x2=k.x,y2=k.y;\r\n    b=x2-x1;\r\n    a=y1-y2;\r\n    c=0-a*x1-b*y1;\r\n}\r\n\r\npoint intersection(double_t a1, double_t b1, double_t c1, double_t a2, double_t b2, double_t c2) {\r\n    double_t delta,deltax,deltay;\r\n    delta=a1*b2-a2*b1;\r\n    deltax=b1*c2-c1*b2;\r\n    deltay=a2*c1-a1*c2;\r\n    if(delta==0) cout<<"Error! delta is 0"<<endl;\r\n    assert(delta!=0);\r\n    return point(deltax/delta,deltay/delta);\r\n}\r\n\r\nbool do_they_intersect(point a, point b, point c, point d) {\r\n    double_t e1=s(a,b,c)*s(a,b,d);\r\n    double_t e2=s(c,d,a)*s(c,d,b);\r\n    return (e1<=0 && e2<=0 && (e1<0 || e2<0));\r\n}\r\n\r\ndouble_t dist(point a, point b) {\r\n    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));\r\n}\r\n\r\nbool on_line(point a, point b, point c) {\r\n    return eq(dist(a,c)+dist(c,b),dist(a,b));\r\n}\r\n\r\nvector <point> convex_hull(vector <point> p) {\r\n    int i;\r\n    vector <point> l,u;\r\n    sort(p.begin(),p.end());\r\n    for(i=0;i<(int)(p.size());i++) {\r\n        while((int)(l.size())>=2 && s(l[l.size()-2],l[l.size()-1],p[i])<=0) l.pop_back();\r\n        l.push_back(p[i]);\r\n    }\r\n    for(i=(int)(p.size())-1;i>=0;i--) {\r\n        while((int)(u.size())>=2 && s(u[u.size()-2],u[u.size()-1],p[i])<=0) u.pop_back();\r\n        u.push_back(p[i]);\r\n    }\r\n    l.pop_back();\r\n    u.pop_back();\r\n    for(i=0;i<(int)(u.size());i++) l.push_back(u[i]);\r\n    return l;\r\n}\r\n\r\nvector <point> get_polygons_intersection(vector <point> a, vector <point> b) {\r\n    vector <point> ans;\r\n    int i,j;\r\n    double_t a1,b1,c1,a2,b2,c2;\r\n    for(i=0;i<(int)(a.size());i++) {\r\n        if(is_it_in(b,a[i])) ans.push_back(a[i]);\r\n    }\r\n    for(i=0;i<(int)(b.size());i++) {\r\n        if(is_it_in(a,b[i])) ans.push_back(b[i]);\r\n    }\r\n    if(!a.empty()) a.push_back(a[0]);\r\n    if(!b.empty()) b.push_back(b[0]);\r\n    for(i=0;i<(int)(a.size())-1;i++) for(j=0;j<(int)(b.size())-1;j++) {\r\n        if(do_they_intersect(a[i],a[i+1],b[j],b[j+1])) {\r\n            get_equation(a[i],a[i+1],a1,b1,c1);\r\n            get_equation(b[j],b[j+1],a2,b2,c2);\r\n            ans.push_back(intersection(a1,b1,c1,a2,b2,c2));\r\n        }\r\n    }\r\n    return convex_hull(ans);\r\n}\r\n\r\ndouble_t solve(int mask) {\r\n    //cout<<"Mask: "<<mask<<endl;\r\n    vector <point> p;\r\n    int i,cnt=0;\r\n    /*p.push_back(point(-200,-200));\r\n    p.push_back(point(200,-200));\r\n    p.push_back(point(200,200));\r\n    p.push_back(point(-200,200));\r\n    p=convex_hull(p);*/\r\n    /*for(i=0;i<(int)(p.size());i++) {\r\n        cout<<p[i].x<<\' \'<<p[i].y<<endl;\r\n    }*/\r\n    for(i=0;i<n;i++) {\r\n        if(mask&(1<<i)) {\r\n            ++cnt;\r\n            p=pts[i+1];\r\n            ++i;\r\n            break;\r\n        }\r\n    }\r\n    for(;i<n;i++) {\r\n        if(mask&(1<<i)) {\r\n            ++cnt;\r\n            //cout<<"Now try with i = "<<i<<endl;\r\n            p=get_polygons_intersection(p,pts[i+1]);\r\n            //cout<<"Ready with i = "<<i<<endl;\r\n        }\r\n    }\r\n    //cout<<cnt<<endl;\r\n    //if(cnt==2) cout<<get_area(p)<<endl;\r\n    /*if(mask==3) {\r\n        //p=get_polygons_intersection(pts[1],pts[2]);\r\n        for(i=0;i<(int)(p.size());i++) {\r\n            cout<<p[i].x<<\' \'<<p[i].y<<endl;\r\n        }\r\n    }*/\r\n    //if(cnt==1) cout<<get_area(p)<<endl;\r\n    if(cnt&1) return get_area(p);\r\n    else return (-1)*get_area(p);\r\n}\r\n\r\nint main() {\r\n    //ios_base::sync_with_stdio(false);\r\n    //cin.tie(NULL);\r\n    int i,j,z;\r\n    /*point p1=point(-40,20),p2=point(-30,60),p3=point(-40,30),p4=point(-20,40);\r\n    double_t a1,b1,c1,a2,b2,c2;\r\n    get_equation(p1,p2,a1,b1,c1);\r\n    get_equation(p3,p4,a2,b2,c2);\r\n    point p5=intersection(a1,b1,c1,a2,b2,c2);\r\n    cout<<p5.x<<\' \'<<p5.y<<endl;*/\r\n\r\n    cin>>n;\r\n    for(i=1;i<=n;i++) {\r\n        cin>>center[i].x>>center[i].y;\r\n        cin>>pt[i].x>>pt[i].y;\r\n        //pts[i].push_back(pt[i]);\r\n        d=dist(center[i],pt[i]);\r\n        for(j=-200;j<=200;j++) for(z=-200;z<=200;z++) {\r\n            if(eq(d,dist(center[i],point(j,z))) && eq(0,s(pt[i],center[i],point(j,z)))) {\r\n                pts[i].push_back(point(j,z));\r\n                break;\r\n            }\r\n        }\r\n        //cout<<pts[i].size()<<endl;\r\n        for(j=-200;j<=200;j++) for(z=-200;z<=200;z++) {\r\n            if(eq(d,dist(point(j,z),center[i])) && eq(dist(point(j,z),pts[i][0]),dist(point(j,z),pts[i][1]))) pts[i].push_back(point(j,z));\r\n        }\r\n        pts[i]=convex_hull(pts[i]);\r\n        /*cout<<"pts [ "<<i<<" ]: ";\r\n        for(j=0;j<(int)(pts[i].size());j++) cout<<"("<<pts[i][j].x<<", "<<pts[i][j].y<<"); ";\r\n        cout<<endl;*/\r\n    }\r\n\r\n    for(i=0;i<(1<<n);i++) {\r\n        ans+=solve(i);\r\n    }\r\n\r\n    down=(long long)(ans);\r\n    up=down+1;\r\n    if(up-ans<=ans-down) cout<<up<<endl;\r\n    else cout<<down<<endl;\r\n\r\n    return 0;\r\n}\r\n/**\r\n3\r\n-35 45 -50 50\r\n-15 35 -40 20\r\n-40 30 -30 20\r\n**/\r\n'
p3
tp4
stp5
.