読者です 読者をやめる 読者になる 読者になる

Area of Polygons (AOJ1242)

スライスするだけ・・・と思っていたら結構ミスった
スライスするとき,+-epsして点と絶対に被らないようにすれば交点のx座標を列挙した時個数は偶数になる([0,1],[2,3]..みたいになる)し,x+epsとx+1-epsの交点は順に対応することがわかる.

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define X real()
#define Y imag()
using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef vector<P> Pol;
typedef pair<int,int> Pi;
D eps=1e-9;
bool eq(D a,D b){return abs(a-b)<eps;}
int sig(D x){return eq(x,0)?0:(x>0?1:-1);}
D dot(P a,P b){return real(conj(a)*b);}
D cro(P a,P b){return imag(conj(a)*b);}
int ccw(P a,P b,P c){
	if(sig(cro(b-a,c-a))==1) return 1;
	if(sig(cro(b-a,c-a))==-1) return -1;
	if(eq(abs(a-c)+abs(c-b),abs(a-b))) return 0;
	if(eq(abs(a-b)+abs(c-b),abs(a-c))) return -2;
	return 2;
}
bool ispal(L a,L b){
	return sig(cro(a.fs-a.sc,b.fs-b.sc))==0;
}
bool iLSex(L l,L s){
	return sig(cro(l.sc-l.fs,s.fs-l.fs)*cro(l.sc-l.fs,s.sc-l.fs))<0;
}
P intLL(L a,L b){
	D t=cro(a.sc-a.fs,a.sc-b.fs)/cro(a.sc-a.fs,b.sc-b.fs);
	return b.fs+t*(b.sc-b.fs);
}
int len(vector<Pi> vc){
	int N=vc.size();
	if(N==0) return 0;
	sort(all(vc));
	int ret=0;
	int l=vc[0].fs,r=vc[0].sc;
	rep(i,N){
		if(r<vc[i].fs){
			ret+=r-l;
			l=vc[i].fs;
			r=vc[i].sc;
		}else{
			chmax(r,vc[i].sc);
		}
	}
	ret+=r-l;
	return ret;
}
int N;
vector<Pi> segs[4001];
Pol pol; 
vector<D> enumxs(Pol pol,D y){
	L l=L(P(0,y),P(1,y));
	vector<D> ds;
	int N=pol.size();
	rep(i,N){
		L s=L(pol[i],(pol[(i+1)%N]));
		if(!ispal(l,s)&&iLSex(l,s)) ds.pb(intLL(l,s).X);
	}
	sort(all(ds));
	return ds;
}
int main(){
	while(true){
		cin>>N;
		if(N==0) break;
		pol.clear();
		rep(i,N){
			int x,y;
			cin>>x>>y;
			pol.pb(P(x,y));
		}
		int ans=0;
		for(int y=-2000;y<2000;y++){
			vector<D> a=enumxs(pol,y+eps*100);
			vector<D> b=enumxs(pol,y+1-eps*100);
			assert(a.size()==b.size());
			int K=a.size();
			assert(K%2==0);
			vector<Pi> segs;
			rep(i,K/2){
				int le=floor(min(a[i*2],b[i*2])+eps),ri=ceil(max(a[i*2+1],b[i*2+1])-eps);
				segs.pb(Pi(le,ri));
			}
			ans+=len(segs);
/*			if(segs.size()){
				show(y);
				for(Pi p:segs) printf("(%d,%d)  ",p.fs,p.sc);
				puts("");
			}*/
		}
		cout<<ans<<endl;
	}
}