Gym 101606B - Breaking Biscuits - [凸包+旋转卡壳][凸包的宽度]
2024-10-19 03:33:38
题目链接:https://codeforces.com/gym/101606/problem/B
题解:
对于给出的 $n$ 个点,先求这些点的凸包,然后用旋转卡壳求出凸包的宽度(Width (minimum width) of a convex polygon)即可。
旋转卡壳求凸包的宽度和求凸包的直径(Diameter (maximum width) of a convex polygon)差不多。
AC代码:
#include<bits/stdc++.h>
#define mk make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
const double eps=1e-;
const double INF=1e18; int Sign(double x)
{
if(x<-eps) return -;
if(x>eps) return ;
return ;
}
int Cmp(double x,double y){return Sign(x-y);} struct Point
{
double x,y;
Point(double _x=,double _y=):x(_x),y(_y){}
Point operator+(const Point &o)const{return Point(x+o.x,y+o.y);}
Point operator-(const Point &o)const{return Point(x-o.x,y-o.y);}
Point operator*(double k)const{return Point(x*k,y*k);}
Point operator/(double k)const{return Point(x/k,y/k);}
int operator==(const Point &o)const{return Cmp(x,o.x)== && Cmp(y,o.y)==;}
bool operator<(const Point &o)const
{
int sgn=Cmp(x,o.x);
if(sgn==-) return ;
else if(sgn==) return ;
else return Cmp(y,o.y)==-;
}
void print(){printf("%.11f %.11f\n",x,y);}
};
typedef Point Vctor; //叉积
double Cross(Vctor A,Vctor B){return A.x*B.y-A.y*B.x;}
double Cross(Point O,Point A,Point B){return Cross(A-O,B-O);} //距离
double Dot(Vctor A,Vctor B){return A.x*B.x+A.y*B.y;}
double Length(Vctor A){return sqrt(Dot(A,A));}
double Length(Point A,Point B){return Length(A-B);} vector<Point> ConvexHull(vector<Point> P,int flag=) //flag=0不严格 flag=1严格
{
if(P.size()<=) return P;
int sz=P.size();
vector<Point> ans(*sz);
sort(P.begin(),P.end());
int now=-;
for(int i=;i<sz;i++)
{
while(now> && Sign(Cross(ans[now]-ans[now-],P[i]-ans[now-]))<flag) now--;
ans[++now]=P[i];
}
int pre=now;
for(int i=sz-;i>=;i--)
{
while(now>pre && Sign(Cross(ans[now]-ans[now-],P[i]-ans[now-]))<flag) now--;
ans[++now]=P[i];
}
ans.resize(now);
return ans;
} double RotatingCalipers(const vector<Point> &P) //旋转卡壳法
{
double ans=INF;
int sz=P.size();
for(int i=,q=;i<sz;i++)
{
int j=(i+)%sz;
while( Cross(P[j]-P[i],P[q]-P[i]) < Cross(P[j]-P[i],P[(q+)%sz]-P[i]) ) q=(q+)%sz;
double d=fabs(Cross(P[i],P[j],P[q]))/Length(P[i],P[j]);
ans=min(ans,d);
}
return ans;
} int n;
vector<Point> P; int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
double x,y; cin>>x>>y;
P.pb(Point(x,y));
}
double ans=RotatingCalipers(ConvexHull(P));
printf("%.8f\n",ans);
}
最新文章
- Ptex源码学习笔记-2
- POJ3974 (manacher)
- Heritrix 3.1.0 源码解析(三十七)
- [itint5]两有序数组的交和并
- MSSql ID自动增长删除数据重1开始
- 贪心+bfs 或者 并查集 Codeforces Round #268 (Div. 2) D
- 使用fliter实现ie下css中rgba的效果
- vue指令v-html示例解析
- Python 接口测试(五)
- Zabbix(一)
- selenium java maven testNg环境搭建
- Effective Java --使类和成员的可访问性最小化
- 【BZOJ3174】[TJOI2013]拯救小矮人(贪心,动态规划)
- 2017.07.09【NOIP提高组】模拟赛B组
- Centos7.1环境下搭建SVN
- 牛客练习赛32-D-MST+tarjin割边
- rac 配置dg完成版
- 字符串方法 split() &; replace()
- date 类型转为varchar
- 使用原生的javascript封装动画函数(有callback功能)