具體步驟看訓(xùn)練指南
( 一 )求解半平面交
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=40010;
const double EPS=1e-10;
struct Point
{
double x,y;
Point(double x=0,double y=0):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+(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
Vector operator*(Vector A,double val)
{
return Vector(A.x*val,A.y*val);
}
struct Line
{
Point p;//直線上的任意一點(diǎn)
Vector v;//方向向量虏束，它的左邊是對(duì)應(yīng)的半平面
double ang;//極角
Line(){}
Line(Point p,Vector v):p(p),v(v){ ang=atan2(v.y,v.x); }
bool operator<(const Line &l) const
{
return ang<l.ang;
}
};
bool onLeft(Line L,Point p)//點(diǎn)p在有向直線的左邊(在線上不算)
{
return cross(L.v,p-L.p)>0;
}
Point getIntersection(Line a,Line b)//兩直線交點(diǎn)奈揍，假定交點(diǎn)唯一存在
{
Vector u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.p+a.v*t;
}
Point p[MAXN];
Line q[MAXN];//雙端隊(duì)列
Line line[MAXN];
Point out[MAXN];
//半平面交的過程
int halfInter(Line *L,int n,Point *poly)
{
sort(L,L+n);
int first,last;
q[first=last=0]=L[0];
for(int i=1;i<n;i++)
{
while(first<last&&!onLeft(L[i],p[last-1])) last--;
while(first<last&&!onLeft(L[i],p[first])) first++;
q[++last]=L[i];
if(fabs(cross(q[last].v,q[last-1].v))<EPS)
{//兩直線平行,取內(nèi)側(cè)的一個(gè)
last--;
if(onLeft(q[last],L[i].p))
{
q[last]=L[i];
}
}
if(first<last) p[last-1]=getIntersection(q[last],q[last-1]);
}
while(first<last&&!onLeft(q[first],p[last-1])) last--;//刪除無用平面
if(last-first<=1) return 0;//空集
p[last]=getIntersection(q[last],q[first]);//計(jì)算首尾兩個(gè)半平面的交點(diǎn)
int m=0;
for(int i=first;i<=last;i++)
{
poly[m++]=p[i];
}
return m;
}
double polyArea(Point *p,int n)
{
double area=0.0;
for(int i=1;i<n-1;i++)
{
area+=cross(p[i]-p[0],p[i+1]-p[0]);
}
return area/2;
}
int main()
{
int n,m=0;
scanf("%d",&n);
double x1,y1,x2,y2;
for(int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
line[m++]=Line(Point(x1,y1),Vector(x2-x1,y2-y1));
}
for(int i=0;i<4;i++)
{
line[m++]=Line(Point(0,0),Vector(1,0));
line[m++]=Line(Point(10000,0),Vector(0,1));
line[m++]=Line(Point(10000,10000),Vector(-1,0));
line[m++]=Line(Point(0,10000),Vector(0,-1));
}
int res=halfInter(line,m,out);
double area=polyArea(out,res);
printf("%.1f\n",area);
return 0;
}
類似的題目：
hdu 1632 Polygons
( 二 )求解多邊形的核
什么是多邊形的內(nèi)核掌唾？
它是平面簡(jiǎn)單多邊形的核是該多邊形內(nèi)部的一個(gè)點(diǎn)集，該點(diǎn)集中任意一點(diǎn)與多邊形邊界上一點(diǎn)的連線都處于這個(gè)多邊形
內(nèi)部干奢。就是一個(gè)在一個(gè)房子里面放一個(gè)攝像 頭痊焊，能將所有的地方監(jiān)視到的放攝像頭的地點(diǎn)的集合即為多邊形的核。
如上圖，第一個(gè)圖是有內(nèi)核的薄啥，比如那個(gè)黑點(diǎn)貌矿，而第二個(gè)圖就不存在內(nèi)核了，無論點(diǎn)在哪里罪佳，總有地區(qū)是看不到的。
求解步驟：
只需要把多邊形的邊當(dāng)做半平面來求即可
但是黑低，判斷點(diǎn)是否在直線的左邊的時(shí)候赘艳，點(diǎn)在直線上的情況也是可以的
同時(shí)，在判斷點(diǎn)在直線的位置時(shí)克握，還用注意下精度
Rotating Scoreboard
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1010;
const double EPS=1e-10;
struct Point
{
double x,y;
Point(double x=0,double y=0):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+(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator *(Vector A,double val)
{
return Vector(A.x*val,A.y*val);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
struct Line
{
Point p;
Vector v;
double ang;
Line(){}
Line(Point p,Vector v):p(p),v(v){ ang=atan2(v.y,v.x); }
bool operator<(const Line &l) const
{
return ang<l.ang;
}
};
int dcmp(double val)
{
if(abs(val)<EPS) return 0;
return val<0?-1:1;
}
bool onLeft(Line line,Point p)//點(diǎn)在直線上也可以,同時(shí)考慮下誤差
{
return dcmp(cross(line.v,p-line.p))>=0;
}
Point getIntersection(Line a,Line b)
{
Vector u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.p+a.v*t;
}
Line line[MAXN];
Line que[MAXN];
Point p[MAXN];
Point ans[MAXN];
Point point[MAXN];
int halfIntersection(Line *L,int n,Point *poly)
{
sort(L,L+n);
int first,last;
que[first=last=0]=L[0];
for(int i=1;i<n;i++)
{
while(first<last&&!onLeft(L[i],p[last-1])) last--;
while(first<last&&!onLeft(L[i],p[first])) first++;
que[++last]=L[i];
if(dcmp(cross(que[last].v,que[last-1].v))==0)
{
last--;
if(onLeft(que[last],L[i].p)) que[last]=L[i];
}
if(first<last) p[last-1]=getIntersection(que[last],que[last-1]);
}
while(first<last&&!onLeft(que[first],p[last-1])) last--;
if(last-first<=1) return 0;
p[last]=getIntersection(que[first],que[last]);
int m=0;
for(int i=first;i<=last;i++)
{
poly[m++]=p[i];
}
return m;
}
int main()
{
int n,t,res;
double x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&point[i].x,&point[i].y);
}
point[n]=point[0];
int cnt=0;
for(int i=1;i<=n;i++)
{
line[cnt++]=Line(point[i-1],point[i-1]-point[i]);
}
res=halfIntersection(line,cnt,ans);
if(res) printf("YES\n");
else printf("NO\n");
}
return 0;
}
( 三 )求解凸多邊形的最大內(nèi)切圓
凸多邊形的最大內(nèi)切圓半徑蕾管？
等價(jià)于從凸多邊形內(nèi)部中找一個(gè)點(diǎn)，使得這個(gè)點(diǎn)到凸多邊形邊界的距離的最小值最大菩暗。
如何求掰曾？
二分半徑加半平面交，將凸多邊形的每條邊向內(nèi)部（垂直方向）收縮半徑r停团，看每條邊的半平面是否還會(huì)交出凸多邊形旷坦。如果推進(jìn)后的半平面交面積小于等于0，則說明距離太大佑稠，否則太小秒梅。
Most Distant Point from the Sea
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1510;
const double EPS=1e-10;
struct Point
{
double x,y;
Point(double x=0,double y=0):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 +(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator*(Vector A,double val)
{
return Vector(A.x*val,A.y*val);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
struct Line
{
Point p;
Vector v;
double ang;
Line(){}
Line(Point p,Vector v):p(p),v(v){ ang=atan2(v.y,v.x); }
bool operator <(const Line &l)const
{
return ang<l.ang;
}
};
int dcmp(double val)
{
if(abs(val)<EPS) return 0;
return val>0?1:-1;
}
bool onLeft(Line line,Point p)
{
return dcmp(cross(line.v,p-line.p))>=0;
}
Point getIntersection(Line a,Line b)
{
Vector u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.p+a.v*t;
}
Point p[MAXN];
Point point[MAXN];
Point change[MAXN];
Line que[MAXN];
Line line[MAXN];
Vector normal[MAXN];
bool halfIntersection(Line *L,int n)
{
sort(L,L+n);
int first,last;
que[first=last=0]=L[0];
for(int i=1;i<n;i++)
{
while(first<last&&!onLeft(L[i],p[last-1])) last--;
while(first<last&&!onLeft(L[i],p[first])) first++;
que[++last]=L[i];
if(dcmp(cross(que[last].v,que[last-1].v))==0)
{
last--;
if(onLeft(que[last],L[i].p)) que[last]=L[i];
}
if(first<last) p[last-1]=getIntersection(que[last],que[last-1]);
}
while(first<last&&!onLeft(que[first],p[last-1])) last--;
if(last-first<=1) return false;
else return true;
}
double polyArea(Point *p,int n)
{
double area=0;
for(int i=1;i<n-1;i++)
{
area+=cross(p[i]-p[0],p[i+1]-p[0]);
}
return area/2;
}
double length(Vector A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
Vector Normal(Vector A)//單位法向量
{
double len=length(A);
return Vector(-A.y/len,A.x/len);
}
int main()
{
int n;
double x,y,lef,rig,mid;
while(scanf("%d",&n)!=EOF,n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&point[i].x,&point[i].y);
}
point[n]=point[0];
for(int i=1;i<=n;i++)
{
normal[i-1]=Normal(point[i]-point[i-1]);
}
lef=0.0;rig=10000.0;
while(lef+EPS<rig)
{
mid=(lef+rig)/2.0;
for(int i=1;i<=n;i++)
{
line[i-1]=Line(point[i-1]+normal[i-1]*mid,point[i]-point[i-1]);//直線向垂直方向平移
}
if(halfIntersection(line,n)) lef=mid;
else rig=mid;
}
printf("%.6f\n",mid);
}
return 0;
}
Feng Shui
題意：
給定多邊形和圓的半徑r，在多邊形內(nèi)安排兩個(gè)圓舌胶，使得兩個(gè)圓覆蓋的區(qū)域盡可能大（重合的部分只算一次）捆蜀，求兩個(gè)圓的圓心坐標(biāo)。
題解：
首先幔嫂，我們應(yīng)該先確定兩個(gè)圓心的活動(dòng)范圍辆它，怎么確定呢？
很簡(jiǎn)單履恩，要使得圓在多邊形內(nèi)部锰茉，我們可以把多邊形沿著邊的垂直方向往內(nèi)縮r個(gè)長(zhǎng)度，然后形成的區(qū)域就是圓心的活動(dòng)范圍似袁。這個(gè)可以用半平面交來求洞辣。
怎么才能使得圓覆蓋的區(qū)域盡可能大？
根據(jù)常識(shí)昙衅，兩個(gè)圓越遠(yuǎn)他們的重合區(qū)域越少扬霜，即覆蓋面積越大，也就是求區(qū)域最遠(yuǎn)的兩點(diǎn)而涉，所以就變成了凸包的直徑問題著瓶。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1510;
const double EPS=1e-10;
int dcmp(double val)
{
if(abs(val)<EPS) return 0;
return val>0?1:-1;
}
struct Point
{
double x,y;
Point(double x=0,double y=0):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 +(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator*(Vector A,double val)
{
return Vector(A.x*val,A.y*val);
}
double cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
struct Line
{
Point p;
Vector v;
double ang;
Line(){}
Line(Point p,Vector v):p(p),v(v){ ang=atan2(v.y,v.x); }
bool operator <(const Line &l)const
{
return ang<l.ang;
}
};
bool onLeft(Line line,Point p)
{
return dcmp(cross(line.v,p-line.p))>=0;
}
Point getIntersection(Line a,Line b)
{
Vector u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.p+a.v*t;
}
Point p1,p2;
Point p[MAXN];
Point point[MAXN];
Point ans[MAXN];
Line que[MAXN];
Line line[MAXN];
int halfIntersection(Line *L,int n,Point *poly)
{
sort(L,L+n);
int first,last;
que[first=last=0]=L[0];
for(int i=1;i<n;i++)
{
while(first<last&&!onLeft(L[i],p[last-1])) last--;
while(first<last&&!onLeft(L[i],p[first])) first++;
que[++last]=L[i];
if(dcmp(cross(que[last].v,que[last-1].v))==0)
{
last--;
if(onLeft(que[last],L[i].p)) que[last]=L[i];
}
if(first<last) p[last-1]=getIntersection(que[last],que[last-1]);
}
while(first<last&&!onLeft(que[first],p[last-1])) last--;
if(last-first<=1) return 0;
p[last]=getIntersection(que[first],que[last]);
int m=0;
for(int i=first;i<=last;i++)
{
poly[m++]=p[i];
}
return m;
}
double length(Vector A)
{
return sqrt(A.x*A.x+A.y*A.y);
}
Vector normal(Vector A)
{
double len=length(A);
return Vector(-A.y/len,A.x/len);
}
void rotateCalipers(Point *ch,int n)
{
double res=-1,area,len;
int up=1;
ch[n]=ch[0];
for(int i=1;i<=n;i++)
{
while(cross(ch[i]-ch[i-1],ch[up+1]-ch[i-1])>cross(ch[i]-ch[i-1],ch[up]-ch[i-1])) up=(up+1)%n;
len=length(ch[up+1]-ch[i]);
if(dcmp(len-res)>=0)
{
p1=ch[up+1];
p2=ch[i];
res=len;
}
len=length(ch[up]-ch[i-1]);
if(dcmp(len-res)>=0)
{
p1=ch[i-1];
p2=ch[up];
res=len;
}
}
}
int main()
{
int n,mid;
double x,y,r,maxr,d;
while(scanf("%d%lf",&n,&r)!=EOF)
{
maxr=0.0;
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&point[i].x,&point[i].y);
}
point[n]=point[0];
for(int i=1;i<=n;i++)
{
line[i-1]=Line(point[i-1]+normal(point[i-1]-point[i])*r,point[i-1]-point[i]);
}
int res=halfIntersection(line,n,ans);
rotateCalipers(ans,res);
printf("%lf %lf %lf %lf\n",p1.x,p1.y,p2.x,p2.y);
}
return 0;
}
