ACM: 109 – SCUD Buster

這題寫出來超想放煙火慶祝的！學了Convex Hull、Graham Scan。生平第一次覺得外積是這麼有用、了不起兼神奇的發明(發現?)啊。只需要乘法，就可以找出兩個向量的角度關係，因此可以避免用到除法的機器浮點數問題，這實在是太神奇了。

一次AC，感動。不過是超嫩的Runtime 0.016，我確定單在sorting就有很大的進步空間。但能夠把一組一組零散的座標，讓電腦連成一個圖形，再算出面積，相當有成就感。

REFERENCES

Graham Scan
Computational Geometry (ppt)

CODE

#include <stdio.h>

#define MAX_KINGDOM 20
#define MAX_VERTEX 100

int k, g[MAX_KINGDOM][MAX_VERTEX][2], gn[MAX_KINGDOM];

int findaim(int x, int y);
int isinside(int kingdom, int x, int y);
float findarea(int kingdom);

int main(){
  int i, j, s, tmp, min;
  int v, mx, my, at;
  int vx[MAX_VERTEX][2], attack[MAX_KINGDOM];
  float tot;
  
  /*Kingdom data*/
  v = 0;
  k = -1;
  while( scanf("%d", &v)!=EOF && v!=-1 ){
    k++;
    
    for(i=0; i<v; i++)
      scanf("%d %d", &vx[i][0], &vx[i][1]);
    
    /*find lowest point; if more than one point are the lowest, find the most left one*/
    min = 0;
    for(i=1; i<v; i++){
      if( vx[i][1] < vx[min][1] )
        min = i;
      else if( vx[i][1] == vx[min][1] )
        if( vx[i][0] < vx[min][0] )
          min = i;
    }
    if( min != 0 ){
      tmp = vx[min][0];
      vx[min][0] = vx[0][0];
      vx[0][0] = tmp;
      
      tmp = vx[min][1];
      vx[min][1] = vx[0][1];
      vx[0][1] = tmp;
    }
    
    /*sort rest points by counter clockwise with outer product*/
    for(i=1; i<v; i++){
      min = i;
      for(j=(i+1); j<v; j++){
        tmp = ( (vx[min][0]-vx[0][0])*(vx[j][1]-vx[0][1]) ) - ( (vx[j][0]-vx[0][0])*(vx[min][1]-vx[0][1]) );
        if( tmp < 0 )
          min = j;
      }/*j*/
      if( min != i ){
        tmp = vx[min][0];
        vx[min][0] = vx[i][0];
        vx[i][0] = tmp;
        
        tmp = vx[min][1];
        vx[min][1] = vx[i][1];
        vx[i][1] = tmp;
      }
    }/*i*/
    
    /*Graham Scan*/
    for(i=0; i<3; i++){
      g[k][i][0] = vx[i][0];
      g[k][i][1] = vx[i][1];
    }
    s = 2; /*s: current stack*/
    for(i; i<v; i++){
      tmp = ( (g[k][s][0]-g[k][s-1][0])*(vx[i][1]-g[k][s-1][1]) ) - ( (vx[i][0]-g[k][s-1][0])*(g[k][s][1]-g[k][s-1][1]) );
      if( tmp > 0 ){
        s++;
        g[k][s][0] = vx[i][0];
        g[k][s][1] = vx[i][1];
      }
      else if( tmp == 0 ){
        g[k][s][0] = vx[i][0];
        g[k][s][1] = vx[i][1];
      }
      else{
        s--;
        i--;
      }
    }
    s++;
    g[k][s][0] = g[k][0][0];
    g[k][s][1] = g[k][0][1];
    gn[k] = s;
    
  }/*while kingdom data input*/
  
  /*Missile attacks*/
  while( scanf("%d %d", &mx, &my) != EOF ){
    at = findaim(mx, my);
    if( at != -1 )
      attack[at] = 1;
  }/*while missile attacks input*/
  
  /*Output*/
  tot = 0.0;
  for(i=0; i<=k; i++)
    if( attack[i] == 1 )
      tot += findarea(i);
  printf("%.2f\n", tot);
  
  exit(0);
}

int findaim(int x, int y){
  int i;
  
  for(i=0; i<=k; i++){
    if( isinside(i, x, y) == 1 )
      return i;
  }/*i: scan through all kingdoms*/

  return -1;
}

int isinside(int kd, int x, int y){
  int i, tmp;
  
  if( y < g[kd][0][1] )
    return 0;
    
  for(i=0; i<gn[kd]; i++){
    tmp = ( ( g[kd][i+1][0]-g[kd][i][0] )*( y-g[kd][i][1] ) ) - ( ( x-g[kd][i][0] )*( g[kd][i+1][1]-g[kd][i][1] ) );
    if( tmp < 0 )
      return 0;
  }
  return 1;
}

float findarea(int kd){
  int i;
  float tmp, sum;
  
  sum = 0.0;
  for(i=1; i<=gn[kd]; i++){
    tmp = ( (g[kd][i-1][0])*(g[kd][i][1]) )-( (g[kd][i][0])*(g[kd][i-1][1]) );
    tmp /= 2;
    sum += tmp;
  }
  
  return sum;
}