题解 P2861 【[USACO06JAN]确保现场Roping the Field】

· · 题解

其实这题不难但是不知道为什么没人过。。

首先看到题目应该是几何题无误（假装很有道理

看到n<=150感觉似乎暴力也能过。。想想边数最多也只有22500条。。。

于是这时候应该马上想到先预处理每条边是否可以连。。。

于是怎么与预处理呢。。。。。。

直接算圆和线段的交点？感觉应该可以但是似乎不怎么好写。。。

考虑题意。。只要线段有部分含于圆内就不能连。。而这个“部分”可以直接认为是线段上与圆心最近的点。。

于是这个预处理就转化成了求点到线段的最小距离。。这个套套公式就好。。感觉三分也可以但是tle了（可能是我写炸了。。

预处理完之后，考虑怎么求答案。。。

要求线段之间不可以相交。。。。

说白了就是不能有1->4 , 2->5这样的线段同时存在。。考虑DP。。那肯定只能区间DP了。。

n<=150的话O(n^3)还是很轻松的吧

推销一波我的博客： http://www.cnblogs.com/Yuigahama/p/8672146.html

然后是代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 20050
#define ept 1e-6
using namespace std;
int n,m;
double R;
struct P{
    double x,y;
}a[200],b[200];
int f[200][200];
bool vis[200][200];
double dis(P u,P v){
    return sqrt((u.x-v.x)*(u.x-v.x)+(u.y-v.y)*(u.y-v.y));
}
double DIS(P u,P v,P w) {  
    double space=0;  
    double a,b,c;  
    a=dis(u,v);
    b=dis(u,w);  
    c=dis(v,w);
    if(c<=ept||b<=ept) {  
        space=0;  
        return space;  
    }  
    if(a<=ept){  
        space=b;  
        return space;  
    }  
    if(c*c>=a*a+b*b){  
        space=b;  
        return space;  
    }  
    if(b*b>=a*a+c*c) {  
        space=c;  
        return space;  
    }  
    double p=(a+b+c)/2;
    double s=sqrt(p*(p-a)*(p-b)*(p-c));
    space=2*s/a; 
    return space;
}
bool judge(P u,P v,P w){
    double d1=DIS(u,v,w);
    if(d1>R) return 0;
    return 1;
}
bool check(P u,P v){
    for(int i=1;i<=m;i++)
        if(judge(u,v,b[i])) return 0;
    return 1;
}
int main(){
    scanf("%d%d%lf",&n,&m,&R);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&a[i].x,&a[i].y);
    for(int i=1;i<=m;i++)
        scanf("%lf%lf",&b[i].x,&b[i].y);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) continue;
            vis[i][j]=check(a[i],a[j]);
        }
    }
    for(int len=3;len<=n;len++){
        for(int i=1;i<=n-len+1;i++){
            for(int j=i;j<=i+len-1;j++)
                f[i][i+len-1]=max(f[i][i+len-1],f[i][j]+f[j][i+len-1]);
            if(vis[i][i+len-1]&&(i!=1||i+len-1!=n))
                f[i][i+len-1]++;
        }
    }
    printf("%d\n",f[1][n]);
    return 0;
}