自动搬运

查看原文

来自洛谷，原作者为

	Iscream2001 **

搬运于2025-08-24 21:42:24，当前版本为作者最后更新于2018-03-29 20:22:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

看到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;
}