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