POJ 1279 Art Gallery 半平面交求多边形核

第一道半平面交,只会写N^2。

将每条边化作一个不等式,ax+by+c>0,所以要固定顺序,方便求解。

半平面交其实就是对一系列的不等式组进行求解可行解。

如果某点在直线右侧,说明那个点在区域内,否则出现在左边,就可能会有交点,将交点求出加入。

//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define ll long long
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
using namespace std; const int MAXN = ;
const double eps = 1e-; struct POINT{
double x;
double y;
POINT() : x(), y() {};
POINT(double _x_, double _y_) : x(_x_), y(_y_) {};
}; struct LINE{
POINT a;
POINT b;
LINE() {};
LINE(POINT _a_, POINT _b_) : a(_a_), b(_b_) {};
}; POINT point[MAXN];//记录最开始的多边形
POINT temp[MAXN]; //临时保存新切割的多边形
POINT ans[MAXN]; //保存新切割出的多边形
LINE lline;
int n,m;//n的原先的点数,m是新切割出的多边形的点数 void Coefficient(const LINE & L, double & A, double & B, double & C){
A = L.b.y - L.a.y;
B = L.a.x - L.b.x;
C = L.b.x * L.a.y - L.a.x * L.b.y;
} double Cross(const POINT & a, const POINT & b, const POINT &o){
return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y);
} POINT Intersection(const LINE & A, const LINE & B){
double A1, B1, C1;
double A2, B2, C2;
Coefficient(A, A1, B1, C1);
Coefficient(B, A2, B2, C2);
POINT temp_point(, );
temp_point.x = -(B2 * C1 - B1 * C2) / (A1 * B2 - A2 * B1);
temp_point.y = (A2 * C1 - A1 * C2) / (A1 * B2 - A2 * B1);
return temp_point;
} //求面积,正为顺时针,和叉积写法有关
double PointArea(POINT p[],int n){
double area = ;
for(int i = ; i < n; ++i)
area += Cross(p[], p[i], p[i+]);
return -area / 2.0;
} void Cut(){ //用直线ax+by+c==0切割多边形
int cut_m = , i;
double a, b, c;
Coefficient(lline, a, b, c);
for(i = ; i <= m; ++i){
if(a * ans[i].x + b*ans[i].y + c >= ) //题目是顺时钟给出点的,所以一个点在直线右边的话,那么带入值就会大于等于0
temp[++cut_m] = ans[i]; //说明这个点还在切割后的多边形内,将其保留
else{
if(a * ans[i - ].x + b * ans[i - ].y + c > ){ //该点不在多边形内,但是它和它相邻的点构成直线与
LINE line1(ans[i - ], ans[i]); //ax+by+c==0所构成的交点可能在新切割出的多边形内,
temp[++cut_m] = Intersection(lline, line1); //所以保留交点
}
if(a * ans[i + ].x + b * ans[i + ].y + c > ){
LINE line1(ans[i + ], ans[i]);
temp[++cut_m] = Intersection(lline, line1); //所以保留交点
}
}
}
for(i = ; i <= cut_m; ++i) ans[i] = temp[i];
ans[cut_m + ] = temp[];
ans[] = temp[cut_m];
m = cut_m;
} void solve(){
int i;
point[] = point[n];
point[n+] = point[];
for(i = ; i <= n + ; ++i){
ans[i] = point[i];
}
m = n;
for(i = ;i <= n; ++i){
lline.a = point[i];
lline.b = point[i + ]; //根据point[i]和point[i+1]确定直线ax+by+c==0
Cut(); //用直线ax+by+c==0切割多边形
}
printf("%.2f\n",Abs(PointArea(ans,m)));
} int main(){
int caseNum,i;
scanf("%d",&caseNum);
while(caseNum--){
scanf("%d",&n);
for(i = ; i <= n; ++i){
scanf("%lf%lf",&point[i].x,&point[i].y);
}
solve();
}
return ;
}
上一篇:MySQL 创始人:写代码比打游戏爽,程序员应多泡开源社区


下一篇:SLua 中使用 Lua 5.3 的编译工程