Geometry的題目,給一個圖形的所有端點座標,和圖形的質心座標,要先找出可以讓圖形「站立」的邊,即當該邊水平時,質心在邊上方並在兩端點之間。一個圖形可能有大於一個可以站立的邊,邊的代號為該邊所經過最大編號(依輸入順序)的點,最後要輸出所有可以站立的邊中,最小的邊代號。
我的做法分為兩部分,第一部分是找convex hull,用graham scan,找出圖形的凸包。第二部分用內積檢查凸包的每個邊是否可以讓圖形站立,即質心到邊兩端點的夾角是否都小於90度(內積>0)。
TIPS
UVa討論區有大量本題測資
CODE
#include <iostream> #include <vector> using namespace std; class vertex{ public: int x, y; }; int n; vertex mass; vector<vertex> v; //original order vector<int> p; //vertices id sorted by polar angle //return outer product of pa->pb int cross(vertex p, vertex a, vertex b){ return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) ); } //return true if pa dot pb > 0 (<90 degree) bool dot(vertex p, vertex a, vertex b){ return ( (a.x - p.x)*(b.x - p.x) + (a.y - p.y)*(b.y - p.y) ) > 0; } int dist(vertex a, vertex b){ return ((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)); } //return true if a should be placed first than b to form counter-clockwise order bool issmaller(vertex p, vertex a, vertex b){ int f = cross(p, a, b); return ( f < 0 || ( f == 0 && dist(p, b) < dist(p, a) ) ); } void quicksort(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; (i<=right) && issmaller(v[p[0]], v[p[left]], v[p[i]]); ++i); for(; (j>left) && !issmaller(v[p[0]], v[p[left]], v[p[j]]); --j); if( i >= j ) break; swap(p[i], p[j]); } swap(p[left], p[j]); quicksort(left, j-1); quicksort(j+1, right); } } int main(){ string s; vertex temp; int i, j, tmp, minv, qn; while( (cin >> s) && (s[0] != '#') ){ scanf("%d%d", &mass.x, &mass.y); v.clear(); p.clear(); i = 0; while( scanf("%d%d", &temp.x, &temp.y) ){ if( temp.x == 0 && temp.y == 0 ) break; v.push_back(temp); p.push_back(i++); } n = v.size(); //find lowest-left for(minv=0, i=1; i<n; ++i) if( (v[i].y < v[minv].y) || (v[i].y == v[minv].y && v[i].x < v[minv].x) ) minv = i; swap(p[minv], p[0]); //sort all vertices counter clockwisely by polar angle quicksort(1, n - 1); //graham scan vector<int> q; //stack of convex hull q.push_back(p[0]); q.push_back(p[1]); for(i=2; i<n; ++i){ qn = q.size() - 1; if( (tmp = cross( v[ q[qn-1] ], v[ q[qn] ], v[ p[i] ] )) > 0 ) q.push_back(p[i]); else if( tmp == 0 ){ q.pop_back(); q.push_back(p[i]); } else{ q.pop_back(); --i; } }//i:all vertices q.push_back(p[0]); //find stable sides qn = q.size(); for(minv=n-1, i=1; i<qn; ++i){ if( (cross(v[q[i-1]], mass, v[q[i]])!=0) && (dot(v[q[i-1]], mass, v[q[i]])>0) && (dot(v[q[i]], mass, v[q[i-1]])>0) ) if( (tmp = (q[i] > q[i-1]) ? q[i] : (n - 1)) < minv ) minv = tmp; } cout << s; for(i=s.size(); i<20; ++i) printf(" "); printf("%d\n", minv + 1); }//while return 0; }
No comments:
Post a Comment