luogu P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows

题解:

二维凸包裸题

按照x坐标为第一关键字,y坐标为第二关键字排序

然后相邻判断叉积用单调队列搞过去

正反都做一次就好了

代码:

#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;++i)
#define dep(i,t,h) for (int i=t;i>=h;--i)
const int N=2e4;
const double eps=1e-;
struct Point{
double x,y,r;
Point(){};
Point(double x1,double y1)
{
x=x1; y=y1;
}
IL void jsr()
{
r=atan2(y,x);
}
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;
}
}p[N],q[N];
IL int dcmp(double x)
{
if (x<-eps) return(-); else
if (x>eps) return(); else return();
}
bool cmp(Point x,Point y)
{
return dcmp(x.x-y.x)<||(dcmp(x.x-y.x)==&&dcmp(x.y-y.y)==-);
}
int n,t;
void push(Point now)
{
while (dcmp((now-q[t])^(q[t]-q[t-]))>) --t;
q[++t]=now;
}
IL double dis(Point x,Point y)
{
return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
rep(i,,n)
{
double x,y;
cin>>x>>y;
p[i]=Point(x,y);
p[i].jsr();
}
sort(p+,p+n+,cmp);
t=;
q[]=q[t]=p[];
rep(i,,n) push(p[i]);
dep(i,n-,) push(p[i]);
double ans=;
rep(i,,t-) ans+=dis(q[i],q[i+]);
printf("%.2lf",ans);
return ;
}
上一篇:oracle自治事务(PRAGMA AUTONOMOUS_TRANSACTION)


下一篇:swift - tableview 滚动到指定位置