AOJ 2448: Area Folding

右手法だか左手法だかいうやつ。

双対は作る必要がないが、だからと言ってそんなに楽というわけでもない。
これ結構面倒なのに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);
}