参考了神仙的博客
基本图形之间的操作：
view code
namespace CG{
//--------------------准备工作--------------------
const double eps=1e-6;
const double pi=acos(-1.0);
struct pt{
double x,y;
pt(double _x=0,double _y=0){x=_x;y=_y;}
};//点或向量
struct line{
pt s,t;
line(pt _s=pt(0,0),pt _t=pt(0,0)){s=_s;t=_t;}
};//两点式直线/线段
inline int dcmp(double x){return x<-eps?-1:(x>eps?1:0);}
inline double Abs(double x){return x*dcmp(x);}//绝对值
//-----------------向量基本运算--------------------
inline double len(pt a){return a.x*a.x+a.y*a.y;}
inline double Len(pt a){return sqrt(a.x*a.x+a.y*a.y);}//向量模长
inline pt operator +(pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
inline pt operator -(pt a,pt b){return pt(a.x-b.x,a.y-b.y);}//向量加减
inline pt operator *(pt a,double b){return pt(a.x*b,a.y*b);}//向量数乘
inline double operator *(pt a,pt b){return a.x*b.x+a.y*b.y;}
//点积：结果=0时a,b垂直，夹角>90度则为负数，<90度则为正数
inline double operator ^(pt a,pt b){return a.x*b.y-a.y*b.x;}
//叉积：结果>0表示b在a逆时针方向，=0表示a,b共线，<0表示b在a顺时针方向
//-----------------点与向量的旋转------------------
inline pt rotate(pt a,double theta){
double x=a.x*cos(theta)+a.y*sin(theta);
double y=-a.x*sin(theta)+a.y*cos(theta);
return pt(x,y);
}//将点或向量a绕原点(向量是顶点)顺时针旋转theta的弧度
inline pt rotate_P(pt a,pt b,double theta){
return rotate(a-b,theta)+b;
}//将点a绕点b旋转theta
//---------------点与线之间的关系------------------
//命名技巧：点P(point)，线段S(segment)，直线L(line)
//--------点与点--------
inline bool operator ==(pt a,pt b){return (!dcmp(a.x-b.x))&&(!dcmp(a.y-b.y));}//两点重合
inline double dis_PP(pt a,pt b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}//点a与点b间的距离
//-------点与直线-------
inline bool judge_PL(pt a,line b){
return !dcmp((a-b.s)^(b.t-b.s));
}//判断点是否在直线上
inline double dis_PL(pt a,line b){
return Abs((a-b.s)^(a-b.t))/Len(b.t-b.s);
}//点与直线的距离:面积除以底边长
inline pt Footprint(pt a,line b){
pt x=a-b.s,y=a-b.t,z=b.t-b.s;
double s1=(x*z)/Len(z),s2=-1.0*(y*z)/Len(z);//分别求出AS，AT关于ST的投影
return b.s+z*(s1/(s1+s2));
}//点A关于直线ST的垂足
inline pt Symmetry_PL(pt a,line b){
return a+(Footprint(a,b)-a)*2.0;
}//点a关于直线b的对称点
//-------点与线段-------
inline bool judge_PS(pt a,line b){
return (!dcmp((a-b.s)^(b.t-b.s)))&&(dcmp((a-b.s)*(a-b.t))<=0);
}//判断点是否在线段上
inline double dis_PS(pt a,line b){
pt x=a-b.s,y=a-b.t,z=b.t-b.s;
if(x*z<0) return Len(x);//距离左端点最近
if(y*z>0) return Len(y);//距离右端点最近
return dis_PL(a,b);
}//点与线段的距离
inline pt point_PS(pt a,line b){
pt x=a-b.s,y=a-b.t,z=b.t-b.s;
if(x*z<0) return b.s;//距离左端点最近
if(y*z>0) return b.t;//距离右端点最近
return Footprint(a,b);
}//点a在线段b上距离最近的点
//------------线与线---------
inline pt cross_LL(line a,line b){
pt x=a.t-a.s,y=b.t-b.s,z=a.s-b.s;
return a.s+x*((y^z)/(x^y));
}
inline bool judge_cross_SL(line a,line b){
return judge_PS(cross_LL(a,b),a);//看交点是否在线段上即可
}//判断线段a与直线b是否相交
inline bool judge_cross_SS(line a,line b){
double s1=(a.t-a.s)^(b.s-a.s),s2=(a.t-a.s)^(b.t-a.s);
double s3=(b.t-b.s)^(a.s-b.s),s4=(b.t-b.s)^(a.t-b.s);
return dcmp(s1)*dcmp(s2)<0&&dcmp(s3)*dcmp(s4)<0;//a的端点在b的两侧且b的端点在a的两侧
}//判断两线段是否相交
//----------多边形------------
struct poly{
vector<pt> pts;
inline int include(pt a){//PIP
int n=pts.size(),cnt=0;
for(int i=0;i<n;++i){
pt s=pts[i],t=i<n-1?pts[i+1]:pts[0];
if(judge_PL(a,line(s,t))) return 2;
if(a.y-min(s.y,t.y)>=-eps&&a.y-max(s.y,t.y)<=eps){
double nx=s.x+(a.y-s.y)*(t.x-s.x)/(t.y-s.y);
if(a.x-nx<=-eps) cnt++;
}
}
return cnt&1;
}//0:在多边形外,1:在多边形内，2：在多边形的边上
inline double area(){
double ans=0;
for(int i=0;i<pts.size();++i) ans+=pts[i]^pts[i<pts.size()-1?i+1:0];
return ans/2;
}
inline bool Left(pt x,pt l,pt r){
return dcmp((l-x)^(r-x))<=0;
}//xl是否在xr左侧
inline int include_bs(pt p){
int n=pts.size();
if(!Left(pts[0],p,pts[1])) return 0;
if(!Left(pts[0],pts[n-1],p)) return 0;
if(judge_PL(p,line(pts[0],pts[1]))) return 2;
if(judge_PL(p,line(pts[0],pts[n-1]))) return 2;
int l=1,r=n-2,ans=1;
while(l<=r){
int mid=(l+r)>>1;
if(!Left(pts[0],pts[mid],p)) l=mid+1,ans=mid;
else r=mid-1;
}
if(!Left(pts[ans],p,pts[ans+1])) return 0;
if(judge_PL(p,line(pts[ans],pts[ans+1]))) return 2;
return 1;
}//二分法
};
}
using namespace CG;
凸包：
Graham算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const double eps=1e-8;
struct pt{
double x,y;
pt(double _x=0,double _y=0){x=_x;y=_y;}
};
struct line{
pt s,t;
line(pt _s=pt(0,0),pt _t=pt(0,0)){s=_s;t=_t;}
};
inline int dcmp(double x){return x<-eps?-1:(x>eps?1:0);}
inline pt operator -(pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
inline double operator ^(pt a,pt b){return a.x*b.y-a.y*b.x;}
inline double dis_PP(pt a,pt b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int n,top;
pt p[N],stk[N];
inline bool cmp(pt x,pt y){
int pd=dcmp((x-p[1])^(y-p[1]));
if(pd>0) return true;
if(pd==0&&dis_PP(x,p[1])<dis_PP(y,p[1])) return true;
return false;
}
inline double Graham(){
for(int i=2;i<=n;++i) if(p[i].y<p[1].y||(p[i].y==p[1].y&&p[i].x<p[1].x)) swap(p[1],p[i]);
stk[++top]=p[1];
sort(p+2,p+n+1,cmp);
for(int i=2;i<=n;++i){
while(top>1){
if(dcmp((stk[top]-stk[top-1])^(p[i]-stk[top]))<0) --top;
else if(dcmp((stk[top]-stk[top-1])^(p[i]-stk[top]))==0&&dis_PP(stk[top-1],stk[top])>dis_PP(stk[top-1],p[i])) --top;
else break;
}
stk[++top]=p[i];
}
stk[++top]=p[1];
double ans=0;
for(int i=2;i<=top;++i) ans+=dis_PP(stk[i-1],stk[i]);
return ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
printf("%.2lf\n",Graham());
return 0;
}
Andrew算法
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const double eps=1e-8;
struct pt{
double x,y;
pt(double _x=0,double _y=0){x=_x;y=_y;}
};
inline int dcmp(double x){return (x>eps)?1:(x<-eps?-1:0);}
inline pt operator -(pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
inline double operator ^(pt a,pt b){return a.x*b.y-a.y*b.x;}
inline bool cmp(pt a,pt b){return (a.x!=b.x)?a.x<b.x:a.y<b.y;}
inline double dis_PP(pt a,pt b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline int Andrew(pt *p,pt *q,int n){
sort(p+1,p+n+1,cmp);
int top=0;
q[++top]=p[1];
for(int i=2;i<=n;++i){
while(top>=2&&((q[top-1]-q[top])^(p[i]-q[top]))>=0) top--;
q[++top]=p[i];
}
int now=top;
for(int i=n-1;i>=1;--i){
while(top>now&&((q[top-1]-q[top])^(p[i]-q[top]))>=0) top--;
q[++top]=p[i];
}
if(n>1) --top;
return top;
}
int n;
pt p[N],q[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
int tot=Andrew(p,q,n);
double ans=0;
for(int i=2;i<=tot;++i) ans+=dis_PP(q[i],q[i-1]);ans+=dis_PP(q[1],q[tot]);
printf("%.2lf\n",ans);
return 0;
}
旋转卡壳求凸包直径
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct pt{
int x,y;
pt(int _x=0,int _y=0){x=_x;y=_y;}
};
inline pt operator -(pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
inline int len(pt a){return a.x*a.x+a.y*a.y;}
inline int operator ^(pt a,pt b){return a.x*b.y-a.y*b.x;}
inline bool cmp(pt a,pt b){return (a.x!=b.x)?a.x<b.x:a.y<b.y;}
inline int Andrew(pt *p,pt *q,int n){
int top=0;
sort(p+1,p+n+1,cmp);
q[++top]=p[1];
for(int i=2;i<=n;++i){
while(top>=2&&((q[top-1]-q[top])^(p[i]-q[top]))>=0) --top;
q[++top]=p[i];
}
int now=top;
for(int i=n-1;i>=1;--i){
while(top>now&&((q[top-1]-q[top])^(p[i]-q[top]))>=0) --top;
q[++top]=p[i];
}
if(n>1) --top;
return top;
}
inline int S(pt x,pt y,pt z){return abs((z-x)^(y-x));}
inline int nxt(int i,int n){return i<n?i+1:1;}
inline int diameter(pt *p,int n){
int ans=0;
for(int i=1,j=2;i<=n;++i){
for(;;j=nxt(j,n)){
if(S(p[nxt(j,n)],p[i],p[nxt(i,n)])<=S(p[j],p[i],p[nxt(i,n)])){
ans=max(ans,len(p[j]-p[i]));
ans=max(ans,len(p[j]-p[nxt(i,n)]));
break;
}
}
}
return ans;
}
int n;
pt p[N],q[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y);
int tot=Andrew(p,q,n);
printf("%d\n",diameter(q,tot));
return 0;
}
半平面交求凸多边形交的面积
#include<bits/stdc++.h>
using namespace std;
const int N=510;
const double eps=1e-8;
struct pt{
double x,y;
pt(double _x=0,double _y=0){x=_x;y=_y;}
};
struct line{
pt s,t;
line(pt _s=pt(0,0),pt _t=pt(0,0)){s=_s;t=_t;}
}q[N];
int n,m,tot;
inline double angle(const pt &p){return atan2(p.y,p.x);}
inline int dcmp(const double &x){return (x>eps)?1:(x<-eps?-1:0);}
inline pt operator +(const pt &a,const pt &b){return pt(a.x+b.x,a.y+b.y);}
inline pt operator -(const pt &a,const pt &b){return pt(a.x-b.x,a.y-b.y);}
inline double operator ^(const pt &a,const pt &b){return a.x*b.y-a.y*b.x;}
inline pt operator *(const pt &a,const double &x){return pt(a.x*x,a.y*x);}
inline pt operator /(const pt &a,const double &x){return pt(a.x/x,a.y/x);}
inline bool cmp(const line &a,const line &b){
double a1=angle(a.t-a.s),a2=angle(b.t-b.s);
if(dcmp(a2-a1)!=0) return a1<a2;
return dcmp((b.s-a.s)^(b.t-a.s))>0;
}
line li[N];
pt p[N];//p[i]是li[i]与li[i-1]的交点
inline pt cross_LL(const line &a,const line &b){
double s1=(a.s-b.t)^(a.t-b.t),s2=(a.t-b.s)^(a.s-b.s);
return b.s+(b.t-b.s)/(s1+s2)*s2;
}
inline int SI(){
sort(q+1,q+tot+1,cmp);
int len=0;
for(int i=1;i<=tot;++i){
if(i>1&&!dcmp(angle(q[i].t-q[i].s)-angle(q[i-1].t-q[i-1].s))) continue;
q[++len]=q[i];
}
int l=1,r=0;
for(int i=1;i<=len;++i){
while(l<r&&dcmp((q[i].t-p[r])^(q[i].s-p[r]))>0) r--;
while(l<r&&dcmp((q[i].t-p[l+1])^(q[i].s-p[l+1]))>0) l++;
li[++r]=q[i];if(r>l) p[r]=cross_LL(li[r],li[r-1]);
}
while(l<r&&dcmp((q[l].t-p[r])^(q[l].s-p[r]))>0) r--;
p[r+1]=cross_LL(li[r],li[l]);r++;
len=r-l;
for(int i=1,j=l+1;j<=r;++i,++j) p[i]=p[j];
return len;
}
inline double area(int n){
double ans=0;
for(int i=2;i<n;++i) ans+=(p[i+1]-p[1])^(p[i]-p[1]);
return fabs(ans)/2;
}
int main(){
scanf("%d",&n);
while(n--){
scanf("%d",&m);
pt last,st,now;
for(int i=1;i<=m;++i){
scanf("%lf%lf",&now.x,&now.y);
if(i>1) q[++tot]=line(last,now);
else st=now;
last=now;
}
q[++tot]=line(last,st);
}
printf("%.3lf\n",area(SI()));
return 0;
}