首页 > 代码库 > POJ 1279 Art Gallery [半平面交]
POJ 1279 Art Gallery [半平面交]
Art Gallery
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 7324 | Accepted: 2936 |
Description
The art galleries of the new and very futuristic building of the Center for Balkan Cooperation have the form of polygons (not necessarily convex). When a big exhibition is organized, watching over all of the pictures is a big security concern. Your task is that for a given gallery to write a program which finds the surface of the area of the floor, from which each point on the walls of the gallery is visible. On the figure 1. a map of a gallery is given in some co-ordinate system. The area wanted is shaded on the figure 2.
Input
The number of tasks T that your program have to solve will be on the first row of the input file. Input data for each task start with an integer N, 5 <= N <= 1500. Each of the next N rows of the input will contain the co-ordinates of a vertex of the polygon ? two integers that fit in 16-bit integer type, separated by a single space. Following the row with the co-ordinates of the last vertex for the task comes the line with the number of vertices for the next test and so on.
Output
For each test you must write on one line the required surface - a number with exactly two digits after the decimal point (the number should be rounded to the second digit after the decimal point).
Sample Input
170 04 44 79 713 -18 -64 -4
Sample Output
80.00
Source
Southeastern Europe 2002
傻逼裸题该死isLSI中sgn的括号打错了RE了无数次40多分钟啊气死我了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#include <vector>using namespace std;typedef long long ll;const int N=1505;const double INF=1e9;const double eps=1e-8;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}inline int sgn(double x){ if(abs(x)<eps) return 0; else return x<0?-1:1;}struct Vector{ double x,y; Vector(double a=0,double b=0):x(a),y(b){} bool operator <(const Vector &a)const{ return sgn(x-a.x)<0||(sgn(x-a.x)==0&&sgn(y-a.y)<0); }};typedef Vector Point;Vector operator +(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator -(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}Vector operator *(Vector a,double b){return Vector(a.x*b,a.y*b);}Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}struct Line{ Point s,t; Line(){} Line(Point a,Point b):s(a),t(b){}};bool isLSI(Line l1,Line l2){ Vector v=l1.t-l1.s,u=l2.s-l1.s,w=l2.t-l1.s; return sgn(Cross(v,u))!=sgn(Cross(v,w));}Point LI(Line a,Line b){ Vector v=a.s-b.s,v1=a.t-a.s,v2=b.t-b.s; double t=Cross(v2,v)/Cross(v1,v2); return a.s+v1*t;}void iniPolygon(Point p[],int &n,double inf){ n=0; p[++n]=Point(inf,inf); p[++n]=Point(inf,-inf); p[++n]=Point(-inf,-inf); p[++n]=Point(-inf,inf);}Point t[N];int tn;void CutPolygon(Point p[],int &n,Point a,Point b){//get the left of a->b tn=0; Point c,d; for(int i=1;i<=n;i++){ c=p[i],d=p[i%n+1]; if(sgn(Cross(b-a,c-a))>=0) t[++tn]=c; if(isLSI(Line(a,b),Line(c,d))) t[++tn]=LI(Line(a,b),Line(c,d)); } n=tn;for(int i=1;i<=n;i++) p[i]=t[i];}double PolygonArea(Point p[],int n){ double s=0; for(int i=2;i<n;i++) s+=Cross(p[i]-p[1],p[i+1]-p[1]); return abs(s/2);}int n,m;Point p[N],q[N];int main(int argc, const char * argv[]){ int T=read(); while(T--){ n=read(); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); iniPolygon(q,m,INF); for(int i=1;i<=n;i++) CutPolygon(q,m,p[i%n+1],p[i]); double ans=PolygonArea(q,m); printf("%.2lf\n",ans); }}
POJ 1279 Art Gallery [半平面交]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。