?

題目傳送門

題意：裸的對(duì)原點(diǎn)的極角排序，凸包貌似不行。

?

/************************************************ * Author :Running_Time * Created Time :2015/11/3 星期二 14:46:47 * File Name :POJ_2007.cpp************************************************/#include <cstdio> #include <algorithm> #include <iostream> #include <sstream> #include <cstring> #include <cmath> #include <string> #include <vector> #include <queue> #include <deque> #include <stack> #include <list> #include <map> #include <set> #include <bitset> #include <cstdlib> #include <ctime> using namespace std;#define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1 typedef long long ll; const int N = 1e5 + 10; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = acos (-1.0); int dcmp(double x) {if (fabs (x) < EPS) return 0;else return x < 0 ? -1 : 1; } struct Point {double x, y;Point () {}Point (double x, double y) : x (x), y (y) {}Point operator - (const Point &r) const { //向量減法return Point (x - r.x, y - r.y);}bool operator == (const Point &r) const { //判斷同一個(gè)點(diǎn)return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0;}bool operator < (const Point &r) const {return x < r.x || (dcmp (x - r.x) == 0 && y < r.y);} }; typedef Point Vector; Point read_point(void) {double x, y;scanf ("%lf%lf", &x, &y);return Point (x, y); } double polar_angle(Vector A) {return atan2 (A.y, A.x); } double dot(Vector A, Vector B) {return A.x * B.x + A.y * B.y; } double cross(Vector A, Vector B) {return A.x * B.y - A.y * B.x; }bool cmp(Point a, Point b) {return cross (a - Point (0, 0), b - Point (0, 0)) > 0; }int main(void) {vector<Point> ps;double x, y;while (scanf ("%lf%lf", &x, &y) == 2) {ps.push_back (Point (x, y));}sort (ps.begin ()+1, ps.end (), cmp);for (int i=0; i<ps.size (); ++i) {printf ("(%.0f,%.0f)\n", ps[i].x, ps[i].y);}//cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/Running-Time/p/4935443.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的简单几何(极角排序) POJ 2007 Scrambled Polygon的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。