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; } }