LA 2512——Art Gallery(半平面交差)

1573 ワード

テーマ:アートギャラリー
标题:1つの建物の中に1つの監視カメラを置いて、建物の中のすべての場所を監視することができて、監視カメラを置くことができる面積がどれだけ大きいかを聞きます.
簡単な半平面交差で、直接テンプレートをセットして面積を求めればいいです.テンプレートは「訓練ガイド」を参考にしています.
入力は時計回りです(最初のサンプルを分析します...)何度もタイトルを読み返してもポイント入力順の情報==をゲットしていないようですが、順番がないと建物が確定しない感じがします..しかし、少なくとも時計回りにACができる...
#include
#include
#include
#include
using namespace std;
const double eps = 1e-8;
const int N = 2001;
struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
};
typedef Point Vector;
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 a){
	return Vector(A.x*a, A.y*a);
}
Vector operator / (Vector A, double a){
	return Vector(A.x/a, A.y/a);
}
int dcmp(double x){
	if(fabs(x) 0;
}
Point GetIntersection(Line a, Line b){
	Vector u = a.P-b.P;
	double t = Det(b.v, u) / Det(a.v, b.v);
	return a.P+a.v*t;
}
Point pt[N], poly[N];
Line L[N], Q[N];
int t, n;
int HalfPlane(){
	sort(L, L+n);
	int head, tail;
	Q[head=tail=0] = L[0];
	for(int i=1; i