当前位置: 代码迷 >> 综合 >> UVALive 4617 Simple Polygon(顺/逆时针输出所有点/极角排序)
  详细解决方案

UVALive 4617 Simple Polygon(顺/逆时针输出所有点/极角排序)

热度:62   发布时间:2023-12-08 10:58:36.0

题目链接:
UVALive 4617 Simple Polygon
题意:
将平面所有点都用上,构成一个多边形,顺时针(或逆时针)输出点的顺序。
分析:
多边形有可能是凸的也有可能是凹的。
先找到最左下角的点(x值优先),然后对其余点以最左下角为基点极角排序。除去最左侧的一系列和point[0]共线的点,其余的点的顺序即是逆时针的点的顺序。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;
const int MAX_N=2010;
const double eps=1e-10;int T,n;
int ans[MAX_N];struct Point{double x,y;
  相关解决方案