0w1

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;
}