POJ 3178 凸包+DP （巨坑）

题意：

POJ 3178 凸包+DP （巨坑）-LMLPHP

思路：

这题巨坑！！！

这题巨坑！！！

这题巨坑！！！

这题巨坑！！！

这题巨坑！！！

（而且没有题解…….5555555……）

只能照着自己想的写了……

先求出来凸包

求凸包的方法呢：先找出来左下角的点然后按照极角排序就OK了。

我用了两边sort

sort(point+1,point+1+n,cmp);

sort(point+2,point+1+n,cmp2);

第一遍sort：

bool cmp(Point a,Point b){

    if(a.x==b.x)return a.y<b.y;

    return a.x<b.x;

}

找出来左下角的点

第二遍sort：

bool cmp2(Point a,Point b){return (long long)(a.x-point[1].x)*(b.y-point[1].y)-(long long)(a.y-point[1].y)*(b.x-point[1].x)>0;}

按照极角找到了凸包（注意是从2号点开始排的序）

Caution： tmd一定要用long long 100000*100000会挂的很惨（我就是有一个点死活过不去幸亏队长比较机智）

两边for暴力枚举一下两个柱子中间是否能连线段（相邻的不能连所以j就从i+2–>n枚举好了）

一定要注意i=1&j=n的情况（否则自己怎么死的都不知道）

ok[i][j]表示i能跟j相连

    for(int i=1;i<=n;i++)

        for(int j=i+2;j<=n;j++)

            if(check(i,j)&&(i!=1||j!=n))ok[i][j]=1;

接下来就要挟坑爹的check函数了……

我的方法是余弦定理乱搞（乱搞都写错了……）

设A, B为线段的两个端点，C为圆心。

圆心到线段的距离<=r就不能连….

怎么求圆心到线段的距离呢这时候要分情况讨论了

1.角A或者角B为钝角这个时候只需判断AC和BC的距离是否大于r就OK了（一开始我没有想到这个挂的很惨）

2.知道三边能够求出cosa（COSA=(B*B+C*C-A*A)/(2*B*C)）

继而倒出SINA（cosa*cosa+sina*sina=1）

这个时候我发现 WOC！我的精度！！！！（OMG）因为有些误差，相切的情况我没有判出来囧么办？ +个eps好了….

于是我就加了个eps

随后就是区间DP了

f[i][j]=max(f[i][k]+f[k][j])+ok[i][j]

（没有人傻到像我一样先枚举i,j,再枚举k了吧……）

（然后我就果断改了啊）

    for(int lenth=2;lenth<=n;lenth++)

        for(int start=1;start<=n;start++){

            int end=start+lenth;

            for(int k=start+1;k<min(end,n);k++)

                f[start][end]=max(f[start][end],f[start][k]+f[k][end]);

            f[start][end]+=ok[start][end];

        }

这题真是步步为坑啊……………….

// by SiriusRen

#include <cmath>

#include <cstdio>

#include <algorithm>

using namespace std;

bool ok[255][255];

int n,g,r,f[255][155];

struct Point{int x,y;}point[255];

struct Circle{int x,y;}circle[255];

bool check(int a,int b){

    double sx=1.0*point[a].x,sy=1.0*point[a].y;

    double ex=1.0*point[b].x,ey=1.0*point[b].y;

    double C=sqrt(1.0*(sy-ey)*(sy-ey)+1.0*(sx-ex)*(sx-ex));

    for(int i=1;i<=g;i++){

        double A=sqrt((circle[i].x-sx)*(circle[i].x-sx)+(circle[i].y-sy)*((circle[i].y-sy)));

        double B=sqrt((circle[i].x-ex)*(circle[i].x-ex)+(circle[i].y-ey)*((circle[i].y-ey)));

        double COSA=(B*B+C*C-A*A)/(2*B*C);

        double COSB=(A*A+C*C-B*B)/(2*A*C);

        if(COSA<1e-10||COSB<1e-10){

            if(A<1.0*r+1e-10||B<1.0*r+1e-10)return 0;

            else continue;

        }

        double SINA=sqrt(1-COSA*COSA);

        double H=B*SINA;

        if(H<1.0*r+1e-10)return 0;

    }

    return 1;

}

bool cmp(Point a,Point b){

    if(a.x==b.x)return a.y<b.y;

    return a.x<b.x;

}

bool cmp2(Point a,Point b){return (long long)(a.x-point[1].x)*(b.y-point[1].y)-(long long)(a.y-point[1].y)*(b.x-point[1].x)>0;}

int main(){

    scanf("%d%d%d",&n,&g,&r);

    for(int i=1;i<=n;i++)

        scanf("%d%d",&point[i].x,&point[i].y);

    sort(point+1,point+1+n,cmp);

    sort(point+2,point+1+n,cmp2);

    for(int i=1;i<=g;i++)

        scanf("%d%d",&circle[i].x,&circle[i].y);

    for(int i=1;i<=n;i++)

        for(int j=i+2;j<=n;j++)

            if(check(i,j)&&(i!=1||j!=n))ok[i][j]=1;

    for(int lenth=2;lenth<=n;lenth++)

        for(int start=1;start<=n;start++){

            int end=start+lenth;

            for(int k=start+1;k<min(end,n);k++)

                f[start][end]=max(f[start][end],f[start][k]+f[k][end]);

            f[start][end]+=ok[start][end];

        }

    printf("%d\n",f[1][n]);

}

整整写了一天啊……….

POJ 3178 凸包+DP （巨坑）-LMLPHP