{"id":353,"date":"2017-12-27T19:39:45","date_gmt":"2017-12-27T11:39:45","guid":{"rendered":"http:\/\/kylelv.com\/?p=353"},"modified":"2017-12-27T20:20:32","modified_gmt":"2017-12-27T12:20:32","slug":"%e5%8d%8a%e5%b9%b3%e9%9d%a2%e4%ba%a4-%e6%a8%a1%e6%9d%bf","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=353","title":{"rendered":"\u534a\u5e73\u9762\u4ea4 — \u6a21\u677f"},"content":{"rendered":"

 <\/p>\n

\u534a\u5e73\u9762\u4ea4<\/h2>\n

 <\/p>\n

\u9898\u76ee\u63cf\u8ff0<\/h2>\n
\"\"<\/p>\n
#include<map>\r\n#include<cmath>\r\n#include<queue>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<iostream>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define ll long long\r\n#define N 1510\r\n#define db double\r\ninline int rd()\r\n{\r\n    int x=0,f=1;char ch=getchar();\r\n    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}\r\n    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\r\n    return x*f;\r\n}\r\nstruct mp{db x,y;}a[N],g[N];\r\nmp operator +(mp a,mp b){return (mp){a.x+b.x,a.y+b.y};}\r\nmp operator -(mp a,mp b){return (mp){a.x-b.x,a.y-b.y};}\r\ndb operator *(mp a,mp b){return a.x*b.y-b.x*a.y;}\r\nmp operator *(db a,mp b){return (mp){b.x*a,b.y*a};}\r\nstruct xx{mp x,y;db af;}b[N],f[N];\r\nbool operator <(xx a,xx b){return a.af==b.af?a.y*(b.x-a.x)<0:a.af<b.af;}\r\nint T,n;\r\nbool fl;\r\nmp Q(xx a,xx b)\r\n{\r\n    db t=a.y*b.y;\r\n    if(!t){puts(\"0.00\");fl=1;}\r\n    return (b.y*(a.x-b.x))\/t*a.y+a.x;\r\n}\r\nvoid sol()\r\n{\r\n    fl=0;n=rd();\r\n    for(int i=1;i<=n;i++){a[i].x=rd();a[i].y=rd();}\r\n    reverse(a+1,a+n+1);\r\n    a[n+1]=a[1];\r\n    for(int i=1;i<=n;i++) b[i]=(xx){a[i],a[i+1]-a[i],atan2((a[i+1]-a[i]).y,(a[i+1]-a[i]).x)};\r\n    sort(b+1,b+n+1);\r\n    int l=1,r=0;\r\n    for(int i=1;i<=n;i++)\r\n    {\r\n        if(i==1||b[i].af>b[i-1].af)\r\n        {\r\n            xx x=b[i];\r\n            while(l<r&&x.y*(g[r]-x.x)<=0) r--;\r\n            while(l<r&&x.y*(g[l+1]-x.x)<=0) l++;\r\n            f[++r]=x;\r\n            if(l<r) g[r]=Q(f[r-1],x);\r\n            if(fl) return;\r\n        }\r\n    }\r\n    g[l]=g[r+1]=Q(f[l],f[r]);\r\n    if(fl) return;\r\n    db ans=0;\r\n    for(int i=l;i<=r;i++) ans+=g[i]*g[i+1];\r\n    printf(\"%.2lf\\n\",abs(ans)*1.0\/2);\r\n}\r\nint main()\r\n{\r\n    T=rd();\r\n    while(T--) sol();\r\n    return 0;\r\n}\r\n\/*\r\n1\r\n7\r\n0 0\r\n4 4\r\n4 7\r\n9 7\r\n13 -1\r\n8 -6\r\n4 -4\r\n \r\n*\/<\/pre>\n
 <\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
  \u534a\u5e73\u9762\u4ea4   \u9898\u76ee\u63cf\u8ff0 #include<map> #include&lt […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[31,19],"class_list":["post-353","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-31","tag-19"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/353","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=353"}],"version-history":[{"count":3,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions"}],"predecessor-version":[{"id":360,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/353\/revisions\/360"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=353"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=353"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=353"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}