AOJProblem Set from CGL 問5～9 - c21coterie @ ウィキ

Segments/Lines - Cross Point

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C
平面上の２線分の交点を求める問題。

#include<stdio.h>
#include<math.h>
 
void calcPoint(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
	double dx1,dy1,dx2,dy2,dx23,dy23,t;
	dx1=x1-x0;
	dy1=y1-y0;
	dx2=x2-x0;
	dy2=y2-y0;
	dx23=x3-x2;
	dy23=y3-y2;
	t=(dx1*dy2-dx2*dy1)/(dx23*dy1-dy23*dx1);
	printf("%.10lf %.10lf\n",x2+t*dx23,y2+t*dy23);
}


int main(){
	double x0,y0,x1,y1,x2,y2,x3,y3;
	double dx1,dx3,dy1,dy3;
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
 		scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
		calcPoint(x0,y0,x1,y1,x2,y2,x3,y3);
	}
}

Segments/Lines - Distance

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_D
２線分の距離を計算する問題。
２線分が交差する場合は0で数問前のコードがそのまま流用できるけれど。
２線分が交差しない場合、線分の両端p0,p1とp2,p3とすると角p1p0p2と角p0p1p2が９０度以内なら、p0p1とp2p3の距離の候補はp0p1とp2の距離とかいろいろ場合わけがめんどくさい。
幾何って結構落とし穴が多いと思う。
それとも私の発想が悪いだけなのだろうか？

#include<stdio.h>
#include<math.h>

bool isFlat(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
	double dx1,dy1,dx2,dy2,dx3,dy3,R1,R2;	
	dx1=x1-x0;
	dy1=y1-y0;
	dx2=x2-x0;
	dy2=y2-y0;
	dx3=x3-x0;
	dy3=y3-y0;
	R1=dx1*dx2+dy1*dy2;	
	R2=dx1*dx3+dy1*dy3;
	if(R1<=0&&0<=R2)return true;
	if(R2<=0&&0<=R1)return true;
	return false;
}
 
bool isCrossHerf(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
	double dx1,dy1,dx2,dy2,dx3,dy3;
	dx1=x1-x0;
	dy1=y1-y0;
	dx2=x2-x0;
	dy2=y2-y0;
	dx3=x3-x0;
	dy3=y3-y0;
	double R1=dx1*dy2-dx2*dy1;
	double R2=dx1*dy3-dx3*dy1;
	if(0<R1&&R2<=0)return true;
if(0<=R1&&R2<0)return true;
 	if(0<R2&&R1<=0)return true;
	if(0<=R2&&R1<0)return true;
	if(R1==0&&R2==0){
		bool Hit1=isFlat(x0,y0,x1,y1,x2,y2,x3,y3);
		bool Hit2=isFlat(x1,y1,x0,y0,x2,y2,x3,y3);
		bool Hit3=isFlat(x2,y2,x3,y3,x0,y0,x1,y1);
		bool Hit4=isFlat(x3,y3,x2,y2,x0,y0,x1,y1);
		return Hit1||Hit2||Hit3||Hit4;
	}
	return false;
} 
double calcLenLineToPoint(double x0,double y0,double x1,double y1,double x2,double y2){
	double dx1,dy1,dx2,dy2;
	dx1=x1-x0;
	dy1=y1-y0;
	dx2=x2-x0;
	dy2=y2-y0;
	double len=hypot(dx1,dy1);
double gaiseki=dx1*dy2-dy1*dx2;
	double result=gaiseki/len;
	if(result<0)result=-result; 
	return result;
}
 
double naiseki(double x0,double y0,double x1,double y1,double x2,double y2){
	return (x1-x0)*(x2-x0)+(y1-y0)*(y2-y0);
} 

double calcLen(double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3){
	double len1,len2;
	if(naiseki(x0,y0,x1,y1,x2,y2)>=0&&naiseki(x1,y1,x0,y0,x2,y2)>=0){
		len1=calcLenLineToPoint(x0,y0,x1,y1,x2,y2);
	}else{
		double a=hypot(x2-x0,y2-y0);
		double b=hypot(x2-x1,y2-y1);
		len1=a>b?b:a;
	}
	if(naiseki(x0,y0,x1,y1,x3,y3)>=0&&naiseki(x1,y1,x0,y0,x3,y3)>=0){
		len2=calcLenLineToPoint(x0,y0,x1,y1,x3,y3);
	}else{
		double a=hypot(x3-x0,y3-y0);
 		double b=hypot(x3-x1,y3-y1);
		len2=a>b?b:a;
	}
	return len1>len2?len2:len1;
}

int main(){
	double x0,y0,x1,y1,x2,y2,x3,y3;
	double dx1,dx3,dy1,dy3;
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%lf %lf %lf %lf",&x0,&y0,&x1,&y1);
		scanf("%lf %lf %lf %lf",&x2,&y2,&x3,&y3);
		bool ok=isCrossHerf(x0,y0,x1,y1,x2,y2,x3,y3)&&isCrossHerf(x2,y2,x3,y3,x0,y0,x1,y1);
		double ans=0;
		if(ok==false){
			double len1=calcLen(x0,y0,x1,y1,x2,y2,x3,y3);
			double len2=calcLen(x2,y2,x3,y3,x0,y0,x1,y1);
			ans=len1>len2?len2:len1;
 		}
		printf("%.10lf\n",ans);
	}
}

Polygon - Area

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_A
多角形の面積を計算する問題。

ベクトルの知識から外積で計算すれば面積が出るのでそれだけです。
昔土木の本を図書館で読んでた時にこの計算法を読んだ記憶がある。

#include<stdio.h>
#include<math.h>

int main(){
	double xs[101],ys[101];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lf %lf",&xs[i],&ys[i]);
 	}
	double ans=0;
	for(int i=0;i<n;i++){
		int p1=i;
		int p2=(i+1)%n;
		ans+=(xs[p1]*ys[p2]-xs[p2]*ys[p1])/2;
 	}
	if(ans<0)ans=-ans;
	printf("%.1lf\n",ans);
}

Polygon - Is-Convex

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_B
多角形の連続した３頂点p1,p2,p3がp1p2,p1p3の外積が一つでもp1p2のほうがp1p3より反時計回りな一にあるなら凸多角形ではない。

#include<stdio.h>
#include<math.h>

int main(){
	double xs[101],ys[101];
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lf %lf",&xs[i],&ys[i]);
	}
	bool isOK=true;
 	for(int i=0;i<n;i++){
		int p0=i;
		int p1=(i+1)%n;
		int p2=(i+2)%n;
			double dx1,dy1,dx2,dy2;
			dx1=xs[p1]-xs[p0];
 			dy1=ys[p1]-ys[p0];
			dx2=xs[p2]-xs[p0];
			dy2=ys[p2]-ys[p0];
 			if(dx1*dy2-dx2*dy1<0)isOK=false;
	}
	printf("%d\n",isOK?1:0);
}

Polygon - Polygon-Point Containment

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_3_C
クエリー数の最大が1000と書いてあったのに実際は１０００以上あってはまった。
これで中々解けなくても仕事じゃあるまいし私に落ち度はないと思う。
AOJ側のミスだと思います

#include<stdio.h>
#include<math.h>

 
int main(){
	double xs[101],ys[101],rs[10001];
	int n,ans[10001];
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lf %lf",&xs[i],&ys[i]);
 	}
	int q;
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		double gx,gy,R=0;
		scanf("%lf %lf",&gx,&gy);
		bool isPeriphery=false;
		for(int j=0;j<n;j++){
			int p1=j;
			int p2=(j+1)%n;
			double dx1,dy1,dx2,dy2,len1,len2;
			dx1=xs[p1]-gx;
			dy1=ys[p1]-gy;
			dx2=xs[p2]-gx;
			dy2=ys[p2]-gy;
			len1=hypot(dx1,dy1);
			len2=hypot(dx2,dy2);
			double gaiseki=dx1*dy2-dx2*dy1;
			double naiseki=dx1*dx2+dy1*dy2;
 			
			if(naiseki<=0&&gaiseki==0){
				isPeriphery=true;
			}else{
				double aSinVal,sinVal;
				
			if(len1*len2>0){
					sinVal=gaiseki/(len1*len2);
				}else{
					isPeriphery=true;
					break;
				}
				if(sinVal<-1)sinVal=-1;
				if(sinVal>1)sinVal=1;
 				aSinVal=asin(sinVal);
				if(gaiseki>0){
					if(naiseki>=0)R+=aSinVal;
					else R+=M_PI-aSinVal;
				}else{
					if(naiseki>=0)R+=aSinVal;
					else R+=-aSinVal-M_PI;
				}
			}
 		}
		
		int type;
		if(fabs(R-M_PI*2)<0.0001){
			type=2;
		}else{
			type=0;
		}
 
		if(isPeriphery==true){
			type=1;
		}
		rs[i]=R;
		ans[i]=type;
	}
 	for(int i=0;i<q;i++){
		printf("%d\n",ans[i]);
	}
}