●POJ 2284 That Nice Euler Circuit

时间：2024-01-12 23:03:56

题链：

http://poj.org/problem?id=2284

题解：

计算几何，平面图的欧拉定理

欧拉定理：设平面图的定点数为v，边数为e，面数为f，则有 v+f-e=2

即 f=e-v+2

所以$N^2$求出所以线段的交点，并去重，

然后再计算出最后共有多少边，（判断点是否在线段上，是的话则e++）

总的复杂度 $O(N^3)$

代码：

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 350

using namespace std;

const double eps=1e-8;

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

};

typedef Point Vector;

int sign(double x){

	if(-eps<=x&&x<=eps) return 0;

	return x<0?-1:1;

}

bool operator < (const Point &A,const Point &B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}

bool operator == (const Point &A,const Point &B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

Point D[MAXN],V[MAXN*MAXN];

int N;

bool SPI(Point a1,Point a2,Point b1,Point b2){//Segment_Proper_Intersection

	static double c1,c2,c3,c4;

	c1=(a2-a1)^(b1-a1); c2=(a2-a1)^(b2-a1);

	c3=(b2-b1)^(a1-b1); c4=(b2-b1)^(a2-b1);

	return sign(c1*c2)<0&&sign(c3*c4)<0;

}

bool OS(Point P,Point a1,Point a2){//On_Segment

	return sign((P-a1)^(P-a2))==0&&sign((P-a1)*(P-a2))<0;

}

Point GLI(Point P,Vector v,Point Q,Vector w){//Get_Line_Intersection

	static Vector u; u=P-Q;

	return P+v*((w^u)/(v^w));

}

int main(){

	int Case=0,v,e;

	while(scanf("%d",&N)&&N){

		for(int i=1;i<=N;i++)

			scanf("%lf%lf",&D[i].x,&D[i].y),V[i]=D[i];

		N--; v=N; e=N;

		for(int i=1;i<=N;i++)

			for(int j=1;j<i;j++)

				if(SPI(D[j],D[j+1],D[i],D[i+1]))

					V[++v]=GLI(D[j],D[j+1]-D[j],D[i],D[i+1]-D[i]);

		sort(V+1,V+v+1);

		v=unique(V+1,V+v+1)-V-1;

		for(int i=1;i<=v;i++)

			for(int j=1;j<=N;j++)

				if(OS(V[i],D[j],D[j+1])) e++;

		printf("Case %d: There are %d pieces.\n",++Case,e-v+2);

	}

	return 0;

}

　　

相关文章