sdut 2153 Clockwise

链接：

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2153.html

题意：

二维平面内给你n个点，构成n-1个向量（第i和第i+1个点构成第i个向量）

问删除最少的点，使得剩下的点构成的向量按顺序呈顺时针或逆时针。

顺时针：第i个向量顺时针转【0，180）与i+1个向量重合

逆时针：第i个向量逆时针转（0，180】与i+1个向量重合

分析：

把每个向量看作点那么我们就可以把问题转换为lis问题

我们枚举终点来求得答案

记dp【i】【j】为以向量（i，j）为最后一个向量情况下边的最大个数

那么dp【i】【j】=max(dp【i】【j】，dp【k】【i】+1）

其中1<k<j且向量（i，k）顺时针转【0，180）（逆时针转（0，180】）与向量（i，j）重合

判断向量关系就用叉积和点积

ACcode：

#include <bits/stdc++.h>
#define maxn 1005
#define eps 1e-8
using namespace std;
int sgn(double x){
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    Point operator-(const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    double operator^(const Point &b)const{
        return x*b.y-y*b.x;
    }
    double operator*(const Point &b)const{
        return x*b.x+y*b.y;
    }
}my[maxn];
int n,ans1,ans2;
int dp1[maxn][maxn];
int dp2[maxn][maxn];
int fun(int i,int j,int k){
    Point v1,v2;
    v1=my[j]-my[i];
    v2=my[i]-my[k];
    double x=v1^v2;
    int tmp=sgn(x);
    if(tmp>0)return 1;
    if(tmp<0)return 2;
    x=v1*v2;
    if(x>eps)return 1;
    if(x<eps)return 2;

}
int main(){
    while(scanf("%d",&n)&&n){
        ans1=ans2=0;
        memset(dp1,0,sizeof(dp1));
        memset(dp2,0,sizeof(dp2));
        for(int i=1;i<=n;++i){
            int x,y;
            scanf("%d%d",&x,&y);
            my[i]=Point(x,y);
            if(i<n)dp1[i][i+1]=dp2[i][i+1]=1;
        }
        for(int j=2;j<=n;++j)
            for(int i=1;i<j;++i)
                for(int k=1;k<j;++k)
                    if(fun(i,j,k)==1)
                        ans1=dp1[i][j]=max(dp1[i][j],dp1[k][i]+1);
                    else if(fun(i,j,k==2))
                        ans2=dp2[i][j]=max(dp2[i][j],dp2[k][i]+1);
        if(ans1==n-1)puts("C");
        else if(ans2==n-1)puts("CC");
        else if(ans1>=ans2)printf("Remove %d bead(s), C\n",n-ans1-1);
        else printf("Remove %d bead(s), CC\n",n-ans2-1);
        printf("\12");
    }
    return 0;
}