http://poj.org/problem?id=1279
顺时针给你一个多边形...求能看到所有点的面积...用半平面对所有边取交即可,模版题
这里的半平面交是O(n^2)的算法...比较逗比...暴力对每条线段做半平面交...要注意的地方写在注释里了...顺序写反了卡了我好久
/********************* Template ************************/ #include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define EPS 1e-8 #define MAXN 10005 #define MOD (int)1e9+7 #define PI acos(-1.0) #define INF ((1LL)<<50) #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) #define max3(a,b,c) (max(max(a,b),c)) #define min3(a,b,c) (min(min(a,b),c)) #define BUG cout<<"BUG! "<<endl #define LLINE cout<<"------------------"<<endl #define L(t) (t << 1) #define R(t) (t << 1 | 1) #define Mid(a,b) ((a + b) >> 1) #define lowbit(a) (a & -a) #define FIN freopen("in.txt","r",stdin) #pragma comment (linker,"/STACK:102400000,102400000") // typedef long long LL; // typedef unsigned long long ULL; // typedef __int64 LL; // typedef unisigned __int64 ULL; // int gcd(int a,int b){ return b?gcd(b,a%b):a; } // int lcm(int a,int b){ return a*b/gcd(a,b); } /********************* F ************************/ struct POINT{ double x,y; POINT(double _x = 0, double _y = 0):x(_x),y(_y){} }p[MAXN],q[MAXN],t[MAXN]; int n; struct LINE{ double a,b,c; POINT A,B; LINE(POINT _a, POINT _b):A(_a),B(_b){ a=B.y-A.y; b=A.x-B.x; c=B.x*A.y-A.x*B.y; } }; double multiply(POINT sp,POINT ep,POINT op){ //叉积 左+ 右- return (sp.x-op.x) * (ep.y-op.y) - (ep.x-op.x) * (sp.y-op.y); } POINT Intersection(LINE a,LINE b){ //直线交点 double u = fabs(b.A.x * a.a + b.A.y * a.b + a.c); double v = fabs(b.B.x * a.a + b.B.y * a.b + a.c); POINT t; t.x = (b.A.x * v + b.B.x * u) / (u + v); t.y = (b.A.y * v + b.B.y * u) / (u + v); return t; } double Triangle_area(POINT a,POINT b,POINT c){ //求三角形面积(带符号) return multiply(a,b,c)/2; } int main() { //freopen("in.txt","r",stdin); //freopen("outm.txt","w",stdout); int ct = 1; int T; cin>>T; while(T--){ cin>>n; for(int i = 0 ; i < n ; i++) scanf("%lf%lf",&p[i].x,&p[i].y); //暴力对每一个向量作半平面交 ...即将右侧的点和与其他直线的交点加入集合 for(int i = 0 ; i < n ; i++) q[i] = p[i]; int cnt = n; for(int i = 0 ; i < n ; i++){ int c = 0; for(int j = 0 ; j < cnt ; j++){ //点在右侧 if(multiply(p[i],p[(i+1)%n],q[j]) <= EPS) { t[c++] = q[j]; }else { //点在左侧,但是前后线段和该直线有交点 //这个顺序不要写反,否则不是顺时针会WA if(multiply(p[i],p[(i+1)%n],q[(j-1+cnt)%cnt]) < -EPS){ t[c++] = Intersection(LINE(p[i],p[(i+1)%n]) , LINE(q[j],q[(j-1+cnt)%cnt])); } if(multiply(p[i],p[(i+1)%n],q[(j+1)%cnt]) < -EPS){ t[c++] = Intersection(LINE(p[i],p[(i+1)%n]) , LINE(q[j],q[(j+1)%cnt])); } } } for(int j = 0 ; j < c ; j++) q[j] = t[j]; cnt = c; } double area = 0; for(int i = 0 ; i < cnt ; i++){ area += Triangle_area(POINT(0,0),q[i],q[(i+1)%cnt]); } area = fabs(area); printf("%.2lf ",area); } return 0; }