右手法だか左手法だかいうやつ。
双対は作る必要がないが、だからと言ってそんなに楽というわけでもない。
これ結構面倒なのに41人も解いているのもすごいし、3300B台で短いほうから2番目というのもすごい。
#include<stdio.h> #include<algorithm> #include<math.h> #include<vector> using namespace std; const double EPS = 1e-10; const double INF = 1e+10; const double PI = acos(-1); Pt p[110]; int it[110][110]; int ind[110][110]; Pt ip[110][110]; int t[110]; vector<int> g[12000]; vector<Pt> hb; int add(Pt a){ for(int i=0;i<hb.size();i++){ if((a-hb[i]).ABS()<EPS)return i; } hb.push_back(a); return hb.size()-1; } int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++){ double X,Y; scanf("%lf%lf",&X,&Y); p[i]=Pt(X,Y); t[i]=add(p[i]); } for(int i=0;i<a-1;i++){ for(int j=0;j<a-1;j++){ if(i==j)continue; if(iLL(p[i],p[i+1],p[j],p[j+1])>0&&iSS(p[i],p[i+1],p[j],p[j+1])){ it[i][j]=1; ip[i][j]=pLL(p[i],p[i+1],p[j],p[j+1]); ind[i][j]=add(ip[i][j]); } } } int sz=hb.size(); for(int i=0;i<a-1;i++){ vector<pair<double,int> > tmp; tmp.push_back(make_pair(0,t[i])); tmp.push_back(make_pair((p[i+1]-p[i]).ABS(),t[i+1])); for(int j=0;j<a-1;j++){ if(!it[i][j])continue; tmp.push_back(make_pair((ip[i][j]-p[i]).ABS(),ind[i][j])); } std::sort(tmp.begin(),tmp.end()); for(int j=0;j<tmp.size()-1;j++){ if(tmp[j].second==tmp[j+1].second)continue; g[tmp[j].second].push_back(tmp[j+1].second); g[tmp[j+1].second].push_back(tmp[j].second); } } double ret=0; int start=0; for(int i=1;i<sz;i++){ if(hb[start].x>hb[i].x)start=i; } int at=start; Pt vec=Pt(0,-1); while(1){ int to=-1; double val=9999999; double curth=vec.arg(); for(int i=0;i<g[at].size();i++){ double th=(hb[g[at][i]]-hb[at]).arg()-curth; if(th>PI+EPS)th-=2*PI; if(th<-PI+EPS)th+=2*PI; if(val>th){ val=th; to=g[at][i]; } } vec=hb[to]-hb[at]; ret+=hb[at].det(hb[to]); at=to; if(at==start)break; } printf("%.12f\n",ABS(ret)/2); }