0w1

UVA 681 Convex Hull Finding ( 凸包模板 )

UVa Online Judge
沒有變化的單純求凸包。比較特別的要求是起點要印兩次,且必須是 y值最小的,若有多個相同則 x值最小的。這部分很容易解決,將點排序的時候照他要求排就行了。
碎念:以為每次後面都要吐出 -1,沒想到是測資與測資之間啊。。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 512 << 1;

struct Vector{
    int x, y;
    Vector(){}
    Vector(int _x, int _y): x(_x), y(_y){}
    friend Vector operator - (const Vector &a, const Vector &b){
        return Vector( a.x - b.x, a.y - b.y );
    }
    friend int Cross(const Vector &a, const Vector &b){
        return a.x * b.y - a.y * b.x;
    }
    bool operator < (const Vector &oth) const{
        if( y != oth.y ) return y < oth.y;
        return x < oth.x;
    }
    bool operator == (const Vector &oth) const{
        return x == oth.x && y == oth.y;
    }
} p[MAXN];

int n;

void solve(){
    sort( p, p + n );
    n = unique( p, p + n ) - p;
    vector<Vector> ch( n + 1 );
    int m = 0;
    for(int i = 0; i < n; ++i){
        while( m > 1 && Cross( ch[m - 1] - ch[m - 2], p[i] - ch[m - 2] ) <= 0 ) --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] ) <= 0 ) --m;
        ch[ m++ ] = p[i];
    }
    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);
    printf("%d\n", T);
    for(int kase = 1; kase <= T; ++kase){
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d%d", &p[i].x, &p[i].y);
        solve();
        scanf("%d", &n); // n = -1
        if( kase != T ) puts("-1"); // 坑 = =
    }
    return 0;
}