UVA 11626 Convex Hull ( 凸包模板 )
UVa Online Judge
不太懂告訴我們一個點是否在凸包上到底有何意義。。嘛反正也是無恥水過去。注意座標會過大要用ll。
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; typedef long long ll; struct Vector{ int x, y; Vector(){} Vector(int _x, int _y): x(_x), y(_y){} friend bool operator < (const Vector &a, const Vector &b){ if( a.x != b.x ) return a.x < b.x; return a.y < b.y; } friend bool operator == (const Vector &a, const Vector &b){ return a.x == b.x && a.y == b.y; } friend Vector operator - (const Vector &a, const Vector &b){ return Vector( a.x - b.x, a.y - b.y ); } friend ll Cross(const Vector &a, const Vector &b){ // x, y <= 1e9 return (ll)a.x * b.y - (ll)a.y * b.x; } } p[MAXN]; int n; void solve(){ sort( p, p + n ); n = unique( p, p + n ) - p; int m = 0; vector<Vector> ch( n + 1 ); for(int i = 0; i < n; ++i){ while( m > 1 && Cross( ch[m - 1] - ch[m - 2], p[i] - ch[m - 2] ) < 0LL ) --m; ch[ m++ ] = p[i]; } int k = m; for(int i = n - 2; i >= 0; --i){ while( m > k && Cross( ch[m - 1] - ch[m - 2], p[i] - ch[m - 2] ) < 0LL ) --m; ch[ m++ ] = p[i]; } if( n > 1 ) --m; printf("%d\n", m); for(int i = 0; i < m; ++i) printf("%d %d\n", ch[i].x, ch[i].y); } int main(){ int T; scanf("%d", &T); while( T-- ){ scanf("%d", &n); for(int i = 0; i < n; ++i){ char trash[3]; scanf("%d%d%s", &p[i].x, &p[i].y, trash); } solve(); } return 0; }