题目

链接

题意:在一个网格图上,给出$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

最新文章

  1. Android-java基础内部类
  2. CI框架--事务
  3. C:内存分配、内存中五大区
  4. Nutch搜索引擎系列
  5. 一晚上将一个模板整合进了DJANGO
  6. 函数page_rec_get_next_const
  7. WCF 配置服务 (02)
  8. Xcode把应用程序打包成ipa
  9. U3D学习使用笔记(一)
  10. Extjs4.0.7 实现Grid的嵌套
  11. [转]HTTPS连接的前几毫秒发生了什么
  12. android studio 的自动更新问题
  13. jQuery事件 (jQuery实现图片轮播)
  14. 屏蔽eslint代码格式报错
  15. 根据现有的XML文件生成其对应的实体类
  16. PHP性能分析——xhprof(window 安装xhporf)
  17. 围棋规则 - AlphaGO
  18. secFox setting
  19. MySQL存储引擎对比
  20. vue中定义多重样式

热门文章

  1. [TCP/IP] 滑动窗口
  2. js中遍历对象的属性和值的方法
  3. [转帖]Kafka 原理和实战
  4. C++多线程基础学习笔记(十)
  5. sqlce基本语法
  6. StoneTab标签页CAD插件 3.2.2
  7. Makefile中 -I -L -l区别
  8. Python中import导入上一级目录模块及循环import问题的解决
  9. mybatis整合spring下的的各种配置文件
  10. 关于操作git