Gym101635K Blowing Candles
2024-08-31 00:14:03
题目链接:http://codeforces.com/gym/101635
题目大意:
推荐一篇文章:https://blog.csdn.net/wang_heng199/article/details/74477738
该题就是要求凸包的宽度(即平行切线间的最小距离)。
AC代码:
#include <bits/stdc++.h> using namespace std;
const double inf = 2e9;
const double esp = 1e-;
int sgn(double x){
if(fabs(x)<esp) return ;
if(x<) return -;
else return ;
}
struct Point{
double x,y;
Point (double _x=,double _y=){
x=_x,y=_y;
}
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;
}
double operator * (const Point &b) const {
return x*b.x+y*b.y;
}
void input(){
scanf("%lf%lf",&x,&y);
}
};
double dist(Point a,Point b){
return sqrt((a-b)*(a-b));
}
const int maxn = 2e5+;
Point List[maxn];
int Stack[maxn],top;
bool _cmp(Point p1,Point p2){
double tmp=(p1-List[])^(p2-List[]);
if(sgn(tmp)>) return true;
else if(sgn(tmp)== && sgn(dist(p1,List[])-dist(p2,List[])) <= )
return true;
else
return false;
}
void Graham(int n){
Point p0=List[];
int k=;
for(int i=;i<n;i++){
if(p0.y>List[i].y || (p0.y == List[i].y && p0.x > List[i].x)){
p0=List[i];
k=i;
}
}
swap(List[k],List[]);
sort(List+,List+n,_cmp);
if(n==){
top = ;
Stack[]=;
return;
}
if(n==){
top=;
Stack[]=,Stack[]=;
return;
}
Stack[]=,Stack[]=;
top=;
for(int i=;i<n;i++){
while(top> &&
(sgn((List[Stack[top-]]-List[Stack[top-]])^(List[i]-List[Stack[top-]]))<=))
top--;
Stack[top++]=i;
}
}
double rotating_calipers(Point p[],int n){
double ans=inf;
Point v;
int cur=;
for(int i=;i<n;i++){
v=p[i]-p[(i+)%n];
while(sgn(v^(p[(cur+)%n]-p[cur]))<)
cur=(cur+)%n;
ans=min(ans,
((p[cur]-p[(i+)%n])^(p[i]-p[(i+)%n]))/(dist(p[i],p[(i+)%n])));
}
return ans;
}
Point p[maxn];
int main(){
int N,R;
scanf("%d%d",&N,&R);
for(int i=;i<N;i++)
List[i].input(); Graham(N);
for(int i=;i<top;i++)
p[i]=List[Stack[i]];
double ans=rotating_calipers(p,top);
printf("%.16lf\n",ans);
return ;
}
最新文章
- js事件流
- temp--test audio micphone
- Exception in thread “main” com.google.gson.JsonSyntaxException: java.lang.NumberFormatException: empty String
- android 永不关闭toast
- Linux客户/服务器程序设计范式2&mdash;&mdash;并发服务器(进程池)
- BZOJ 3306 树
- Java之对象池
- 【学习笔记】【C语言】逗号运算符
- 将solr3.5整合到Tomcat6.x中
- ssh伪登陆执行远程主机脚本命令 C程序基于ssh passwordless执行远程主机命令及基于配置文件的验证伪登陆执行命令
- c#中(int)、int.Parse()、int.TryParse、Convert.ToInt32的区别
- BZOJ 1652: [Usaco2006 Feb]Treats for the Cows
- 关于new,delete,malloc,free的一些总结
- appium入门元素识别参考
- WinServer-FTP搭建
- Hadoop2.7.6_08_Federation联邦机制
- hdu 5073 有坑+方差贪心
- MyChatRoom——C#自制聊天室
- mysql 约束条件目录
- Ipython使用