山東省第一節約試合C(計算幾何学+dp)

主に状態表示を言います.
ここでの状態は、iで始まることをd(i,j)で表し、jで終わるベクトルで下に進むには少なくともいくつかの点を削除する必要があり、最終的な答えは、各状態に対して最適値を求めることである.
計算ジオメトリの部分は、フォーク積と点積で考慮する必要があります.時計回りと反時計回りに成立する条件は正反対であることが分かった.

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 10000;
const int N = 310;
struct point{
  int x,y;
  point(int x=0,int y=0):x(x),y(y){}
}a[N];
int cross(point A,point b){
  return A.x*b.y-A.y*b.x;
}
int Dot(point A,point b){
  return A.x*b.x+A.y*b.y;
}
int judge(int i,int j,int k){
  point A(a[j].x-a[i].x,a[j].y-a[i].y);
  point B(a[k].x-a[j].x,a[k].y-a[j].y);
  int cro = cross(A,B),dot = Dot(A,B);
  if(cro==0){
     return dot > 0;
  }
  else if(cro>0) return 1;
  return 0;
}
int d[N][N];
int n;
void init(){}
int dp(){
  int res=inf;
  for(int j=n;j>=2;j--)
    for(int i=1;i<j;i++){
      if(j==n) d[i][j]=0;
      else{
        d[i][j]=n-j;
        for(int k=j+1;k<=n;k++){
           if(judge(i,j,k))
            d[i][j]=min(d[i][j],d[j][k]+k-j-1);
        }
      }
      res=min(res,d[i][j]+(j-i-1)+i-1);
   }
  return res;
}
int dp2(){
  int res=inf;
  for(int j=n;j>=2;j--)
    for(int i=1;i<j;i++){
      if(j==n) d[i][j]=0;
      else{
        d[i][j]=n-j;
        for(int k=j+1;k<=n;k++){
           if(!judge(i,j,k))
            d[i][j]=min(d[i][j],d[j][k]+k-j-1);
        }
      }
      res=min(res,d[i][j]+(j-i-1)+i-1);
  }
  return res;
}
int main()
{
    while(scanf("%d",&n)==1 && n){
       for(int i=n;i>=1;i--)
        scanf("%d %d",&a[i].x,&a[i].y);
       init();
       int ans1 = dp();
       init();
       int ans2 = dp2();
       if(!ans1) printf("C
");
       else if(!ans2) printf("CC
");
       else if(ans1<=ans2)
           printf("Remove %d bead(s), C
",ans1);
       else printf("Remove %d bead(s), CC
",ans2);
       printf("
");
    }
    return 0;
}