ACM: 132 - Bumpy Objects

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