UVALive 6859——凸包&&周长
2024-09-05 07:37:41
题目
题意:在一个网格图上,给出$n$个点的坐标,用一个多边形包围这些点(不能接触,且多边形的边只能是对角线或直线),求多边形的最小周长.
分析
对于每个点,我们考虑与之相邻的4个点。一共由 $4 \times N$ 个点,然后求凸包。对凸包上每对相邻的点,优先走对角线,然后走直线。累加长度即可。
#include<bits/stdc++.h>
using namespace std; struct Point{
double x, y;
Point(double x=, double y=):x(x), y(y){}
};
typedef Point Vector;
Vector operator + (Vector A, Vector B){
return Vector(A.x+B.x, A.y+B.y);
}
Vector operator - (Point A, Point B){
return Vector(A.x-B.x, A.y-B.y);
}
Vector operator * (Vector A, double p){
return Vector(A.x * p, A.y * p);
}
Vector operator / (Vector A, double p){
return Vector(A.x / p, A.y / p);
}
bool operator < (const Point& a, const Point& b){
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
double Cross(Vector A, Vector B)
{
return A.x * B.y - A.y * B.x;
} int ConvexHull(Point* p, int n, Point* ch)
{
sort(p, p+n);
int m=;
for(int i = ;i < n;i++)
{
while(m > && Cross(ch[m-] - ch[m-], p[i] - ch[m-]) <= ) m--;
ch[m++] = p[i];
}
int k = m;
for(int i = n-;i >= ;i--)
{
while(m > k && Cross(ch[m-] - ch[m-], p[i] - ch[m-]) <= ) m--;
ch[m++] = p[i];
}
if(n > ) m--;
return m;
} const int maxn = + ;
int n;
Point points[maxn * ], ch[maxn * ]; int main()
{
//printf("%lf\n", sqrt(2) * 4);
while(scanf("%d", &n) == )
{
double x, y;
int cnt = ;
for(int i = ;i < n;i++)
{
scanf("%lf%lf", &x, &y);
points[cnt].x = x+, points[cnt++].y = y;
points[cnt].x = x-, points[cnt++].y = y;
points[cnt].x = x, points[cnt++].y = y+;
points[cnt].x = x, points[cnt++].y = y-;
}
int pcnt = ConvexHull(points, cnt, ch);
double ans = ; //sort(ch, ch + pcnt); //for(int i = 0;i < pcnt;i++) printf("%d: %lf %lf\n", i, ch[i].x, ch[i].y); double dx = fabs(ch[].x - ch[pcnt-].x);
double dy = fabs(ch[].y - ch[pcnt-].y);
if(dx > dy) swap(dx, dy);
ans += dx * sqrt();
ans += (dy - dx); for(int i = ;i < pcnt;i++)
{
double dx = fabs(ch[i].x - ch[i-].x);
double dy = fabs(ch[i].y - ch[i-].y);
if(dx > dy) swap(dx, dy);
ans += dx * sqrt();
ans += (dy - dx); //printf("%lf\n", ans);
}
printf("%lf\n", ans);
}
return ;
}
参考链接:https://blog.csdn.net/qingshui23/article/details/52809736
最新文章
- Android-java基础内部类
- CI框架--事务
- C:内存分配、内存中五大区
- Nutch搜索引擎系列
- 一晚上将一个模板整合进了DJANGO
- 函数page_rec_get_next_const
- WCF 配置服务 (02)
- Xcode把应用程序打包成ipa
- U3D学习使用笔记(一)
- Extjs4.0.7 实现Grid的嵌套
- [转]HTTPS连接的前几毫秒发生了什么
- android studio 的自动更新问题
- jQuery事件 (jQuery实现图片轮播)
- 屏蔽eslint代码格式报错
- 根据现有的XML文件生成其对应的实体类
- PHP性能分析——xhprof(window 安装xhporf)
- 围棋规则 - AlphaGO
- secFox setting
- MySQL存储引擎对比
- vue中定义多重样式