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

AOJ 1256: Crossing Prisms

頑張る。
全面と側面で同じ形であることを知らなくて無駄にコードを書きすぎた。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
int X[2][5];
int Y[2][5];
int L[20];
int R[20];
double EPS=1e-9;
int ABS(int a){return max(a,-a);}
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<20;i++){
			L[i]=R[i]=0;
		}
		for(int i=0;i<a;i++)scanf("%d%d",&X[0][i],&Y[0][i]);
		X[0][a]=X[0][0];
		Y[0][a]=Y[0][0];
		for(int i=0;i<a-1;i++){
			if(Y[0][i]==Y[0][i+1]&&Y[0][i+1]==Y[0][i+2]){
				for(int j=i+1;j<a;j++){
					X[0][j]=X[0][j+1];
					Y[0][j]=Y[0][j+1];
				}
				a--;break;
			}
		}
		int b=a;
		for(int i=0;i<=a;i++){
			X[1][i]=X[0][i];Y[1][i]=Y[0][i];
		}
		double ret=0;
		for(int i=0;i<a;i++){
			if(Y[0][i]==Y[0][i+1]){
				L[Y[0][i]]=ABS(X[0][i]-X[0][i+1]);
			}else{
				double ks=sqrt((Y[0][i]-Y[0][i+1])*(Y[0][i]-Y[0][i+1])+(X[0][i]-X[0][i+1])*(X[0][i]-X[0][i+1]))/ABS(Y[0][i]-Y[0][i+1]);
				double tmp=0;
				for(int j=min(Y[0][i],Y[0][i+1]);j<max(Y[0][i],Y[0][i+1]);j++){
					vector<double>now;
					for(int k=0;k<b;k++){
						if(min(Y[1][k],Y[1][k+1])<=j&&j<max(Y[1][k],Y[1][k+1])){
							now.push_back((double)X[1][k]+(double)(X[1][k+1]-X[1][k])*(j+0.5-Y[1][k])/(Y[1][k+1]-Y[1][k]));
						}
					}
					std::sort(now.begin(),now.end());
					for(int k=0;k<now.size();k++){
						if(k%2)tmp+=now[k];
						else tmp-=now[k];
					}
				}
			//	tmp/=2;
				tmp*=ks;
				ret+=tmp;
			}
		}
for(int i=0;i<b;i++){
			if(Y[1][i]==Y[1][i+1]){
				R[Y[1][i]]=ABS(X[1][i]-X[1][i+1]);
			}else{
				double ks=sqrt((Y[1][i]-Y[1][i+1])*(Y[1][i]-Y[1][i+1])+(X[1][i]-X[1][i+1])*(X[1][i]-X[1][i+1]))/ABS(Y[1][i]-Y[1][i+1]);
				double tmp=0;
				for(int j=min(Y[1][i],Y[1][i+1]);j<max(Y[1][i],Y[1][i+1]);j++){
					vector<double>now;
					for(int k=0;k<a;k++){
						if(min(Y[0][k],Y[0][k+1])<=j&&j<max(Y[0][k],Y[0][k+1])){
							now.push_back((double)X[0][k]+(double)(X[0][k+1]-X[0][k])*(j+0.5-Y[0][k])/(Y[0][k+1]-Y[0][k]));
						}
					}
					std::sort(now.begin(),now.end());
					for(int k=0;k<now.size();k++){
						if(k%2)tmp+=now[k];
						else tmp-=now[k];
					}
				}
			//	tmp/=2;
				tmp*=ks;
				ret+=tmp;
			}
		}
		for(int i=0;i<=10;i++){
			vector<double>v;
			for(int j=0;j<a;j++){
				if(min(Y[0][j],Y[0][j+1])<=i&&i<=max(Y[0][j],Y[0][j+1])){
					if(Y[0][j]==Y[0][j+1]){
						v.push_back(X[0][j]);
						v.push_back(X[0][j+1]);
					}else v.push_back((double)X[0][j]+(double)(X[0][j+1]-X[0][j])*(i-Y[0][j])/(Y[0][j+1]-Y[0][j]));
				}
			}
			std::sort(v.begin(),v.end());
			vector<double>V;
			for(int j=0;j<v.size();j++){
				if(j==0||v[j]-v[j-1]>EPS)V.push_back(v[j]);
			}
			double t1=0;
			if(V.size()==4){
				t1=V[3]+V[1]-V[2]-V[0];
			}else if(V.size()>1){
				t1=V[V.size()-1]-V[0];
			}
			vector<double>w;
			for(int j=0;j<b;j++){
				if(min(Y[1][j],Y[1][j+1])<=i&&i<=max(Y[1][j],Y[1][j+1])){
					if(Y[1][j]==Y[1][j+1]){
						w.push_back(X[1][j]);
						w.push_back(X[1][j+1]);
					}else w.push_back((double)X[1][j]+(double)(X[1][j+1]-X[1][j])*(i-Y[1][j])/(Y[1][j+1]-Y[1][j]));
				}
			}
			std::sort(w.begin(),w.end());
			vector<double>W;
			for(int j=0;j<w.size();j++){
				if(j==0||w[j]-w[j-1]>EPS)W.push_back(w[j]);
			}
			double t2=0;
			if(W.size()==4){
				t2=W[3]+W[1]-W[2]-W[0];
			}else if(W.size()>1){
				t2=W[W.size()-1]-W[0];
			}
	//		printf("%f %f\n",t1,t2);
			ret+=L[i]*t2;
			ret+=R[i]*t1;
			ret-=L[i]*R[i];
		}
		printf("%.12f\n",ret);
	}
}