POJ1279 半平面交模板
题意
以顺时针或逆时针顺序给定一个多边形，求该多边形核的面积
解法
半平面交要求边要按逆时针顺序，首先利用叉积判断给定点顺序为逆时针还是顺时针，然后按逆时针方向建边，最后跑半平面交算法，得到多边形的核。对核中相邻边求交点，利用叉积计算面积。
代码：
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;
const int maxn=2e3+5;
const double eps = 1e-8;
int sgn(double x) {
if(fabs(x) < eps)
return 0;
if(x < 0)
return -1;
return 1;
}
struct Point {
double x,y;
Point() {}
Point(double _x,double _y) {
x = _x;
y = _y;
}
Point operator -(const Point &b)const {
return Point(x - b.x,y - b.y);
}
double operator ^(const Point &b)const {
return x*b.y - y*b.x;
}
double operator *(const Point &b)const {
return x*b.x + y*b.y;
}
Point Rotate(double rad){ //逆时针旋转
return Point(x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad));
}
double angle(){
return atan2(y,x);
}
double len(){
return sqrt(x*x+y*y);
}
};
double xmult(Point p0,Point p1,Point p2) { //p0p1 X p0p2
return (p1-p0)^(p2-p0);
}
double getArea(Point a,Point b,Point c){
return fabs(xmult(a,b,c))/2.0;
}
struct Line{
Point s,t;
double ang;
Line(Point X=Point(),Point Y=Point()){
s=X,t=Y,ang=(Y-X).angle();
}
double getangle(){
return ang=(t-s).angle();
}
};
Point getIntersectPoint(Line a, Line b) {
double a1 = a.s.y - a.t.y, b1 = a.t.x - a.s.x, c1 = a.s.x * a.t.y - a.t.x * a.s.y;
double a2 = b.s.y - b.t.y, b2 = b.t.x - b.s.x, c2 = b.s.x * b.t.y - b.t.x * b.s.y;
return Point((c1*b2-c2*b1)/(a2*b1-a1*b2), (a2*c1-a1*c2)/(a1*b2-a2*b1));
}
Point p[maxn];//存顶点
Point pj[maxn];//存交点
bool judge(int n){//判断是否是逆时针的
double ans=0;
for(int i=1;i<=n-1;i++){
ans+=xmult(p[0],p[i],p[i+1]);
}
return ans>0;
}
bool onRight(Line a,Line b,Line c){
Point jiao=getIntersectPoint(b,c);
if(xmult(a.s,a.t,jiao)<0){
return 1;
}
else{
return 0;
}
}
bool cmpHL(Line a,Line b){
double A=a.getangle(),B=b.getangle();
if(sgn(A-B)==0){//平行的直线将最左边的放后面，便于去重
return xmult(a.s,a.t,b.t)>=0;
}
else{
return A<B;
}
}
vector<Line> getHL(vector<Line> l){
//去除角度相同的，保留最最左的
sort(l.begin(),l.end(),cmpHL);
int n=l.size();
int cnt=0;
for(int i=0;i<=n-2;i++){
if(sgn(l[i].getangle()-l[i+1].getangle())==0){
continue;
}
l[cnt++]=l[i];
}
l[cnt++]=l[n-1];
deque<Line> que;
for(int i=0;i<cnt;i++){
while(que.size()>=2&&onRight(l[i],que[que.size()-1],que[que.size()-2])) que.pop_back();
while(que.size()>=2&&onRight(l[i],que[0],que[1])) que.pop_front();
que.push_back(l[i]);
}
while(que.size()>=3&&onRight(que[0],que[que.size()-1],que[que.size()-2])) que.pop_back();
while(que.size()>=3&&onRight(que[que.size()-1],que[0],que[1])) que.pop_front();
vector<Line> hl;
for(int i=0;i<que.size();i++){
hl.push_back(que[i]);
}
return hl;
}
int main () {
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
vector<Line>l;
if(judge(n)){//已经是逆时针
for(int i=1;i<=n;i++){
l.push_back(Line(p[i],p[i%n+1]));
}
}
else{//是顺时针
for(int i=1;i<=n;i++){
l.push_back(Line(p[i%n+1],p[i]));
}
}
vector<Line> hl=getHL(l);
int lnum=hl.size();
if(lnum>=3){
for(int i=0;i<=lnum-1;i++){
pj[i+1]=getIntersectPoint(hl[i],hl[(i+1)%lnum]);
}
double ans=0;
for(int i=2;i<=lnum-1;i++){
ans+=getArea(pj[1],pj[i],pj[i+1]);
}
printf("%.2f
",ans);
}
else{
puts("0.00");
}
}
}