题目链接: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);
}

最新文章

  1. Ptex源码学习笔记-2
  2. POJ3974 (manacher)
  3. Heritrix 3.1.0 源码解析(三十七)
  4. [itint5]两有序数组的交和并
  5. MSSql ID自动增长删除数据重1开始
  6. 贪心+bfs 或者 并查集 Codeforces Round #268 (Div. 2) D
  7. 使用fliter实现ie下css中rgba的效果
  8. vue指令v-html示例解析
  9. Python 接口测试(五)
  10. Zabbix(一)
  11. selenium java maven testNg环境搭建
  12. Effective Java --使类和成员的可访问性最小化
  13. 【BZOJ3174】[TJOI2013]拯救小矮人(贪心,动态规划)
  14. 2017.07.09【NOIP提高组】模拟赛B组
  15. Centos7.1环境下搭建SVN
  16. 牛客练习赛32-D-MST+tarjin割边
  17. rac 配置dg完成版
  18. 字符串方法 split() &amp; replace()
  19. date 类型转为varchar
  20. 使用原生的javascript封装动画函数(有callback功能)

热门文章

  1. mysql语句实战
  2. A Boring Problem UVALive - 7676 (二项式定理+前缀和)
  3. Stm32 GPIO复习
  4. Ch02 课堂作业
  5. OGG微服务架构入门
  6. 萌新的IDEA_web开发笔记(未完)
  7. TCP-IP详解笔记6
  8. mysql收集统计信息
  9. Datagrip连接Mysql 和Hive
  10. Linux系统xinetd服务启动不了