本文主要是介绍POJ2007 凸包,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:题目链接
这道题目就是模版题,套用凸包的计算模版就行了
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;#define maxn 55
#define pi acos(-1)struct Point
{int x, y;
} point[maxn];bool operator <(const Point &a, const Point &b)
{return atan2(a.y, a.x) < atan2(b.y, b.x);
}double cal(double a)
{if (a < 0)return a + 2 * pi;return a;
}int main()
{scanf("%d%d", &point[0].x, &point[0].y);int n = 0;while (scanf("%d%d", &point[n].x, &point[n].y) != EOF)n++;sort(point, point + n);double temp = 0;point[n] = point[0];int s;for (int i = 0; i < n; i++){double a = cal(atan2(point[i + 1].y, point[i + 1].x) - atan2(point[i].y, point[i].x));if (a > temp){temp = a;s = (i + 1) % n;}}printf("(0,0)\n");for (int i = 0; i < n; i++)printf("(%d,%d)\n", point[(s + i) % n].x, point[(s + i) % n].y);return 0;
}
这篇关于POJ2007 凸包的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!