hdu 6603 Azshara’s deep sea

2019-08-04 by fffasttime·0评论

2019 多校第三场A ，简单计算几何+简单dp

明明n<=400还10组数据，出题人硬说凸包上的点不会很多n^3可过，害我想一整场怎么优化。

题意：n个平面上的木桩，你要选出尽可能多的以凸包上两个不相邻木桩为顶点的线，使这些线互不相交而且不能与给定的g个圆相交。

把与圆相交的线去掉，然后做一个简单的区间dp即可。

```
/*
```
```
Author: fffasttime
```
```
Date:
```
```
 */
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
typedef long long ll;
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
const int N=100010;
```
```
 
```
```
typedef double db;
```
```
const db eps=1e-9;
```
```
bool eq(db x){return fabs(x)<eps;}
```
```
 
```
```
#define Vec const vec &
```
```
#define Point const point &
```
```
struct vec{
```
```
	db x,y;
```

	vec operator+(Vec v)const{return {x+v.x,y+v.y};}

	vec operator-(Vec v)const{return {x-v.x,y-v.y};}

	vec operator*(db t)const{return {x*t,y*t};}

	vec operator/(db t)const{return {x/t,y/t};}

```
 
```

	db operator|(Vec v)const{return x*v.x+y*v.y;}

	db operator&(Vec v)const{return x*v.y-y*v.x;}

	db operator!()const{return sqrt(x*x+y*y);}

```
	bool operator<(vec v)const{
```
```
		return eq(x-v.x)?y<v.y:x<v.x;
```
```
	}
```
```
	void rd(){
```
```
		scanf("%lf%lf",&x,&y);
```
```
	}
```
```
	void prt(){printf("%f %f\n",x,y);}
```
```
};
```
```
typedef vec point;
```

db cross(Vec a, Vec b, Vec c){return b-a&c-a;}

```
 
```

int convex(point *p, int n, point *ans){

```
	sort(p,p+n);
```
```
	int m=0;
```
```
	for (int i=0;i<n;i++){
```

		while (m>1 && cross(ans[m-2],ans[m-1],p[i])<=0) m--;

```
		ans[m++]=p[i];
```
```
	}
```
```
	int k=m;
```
```
	for (int i=n-2;i>=0;i--){
```

		while (m>k && cross(ans[m-2],ans[m-1],p[i])<=0) m--;

		for (int i=0;i<n;i++) a[i][(i+1)%n]=a[i][(i-1+n)%n]=0;

```
		for (int k=2;k<n;k++)
```
```
			for (int i=0;i+k<n;i++){
```
```
				for (int j=i+1;j<i+k;j++){
```

					dp[i][i+k]=max(dp[i][i+k],dp[i][j]+dp[j][i+k]+a[i][i+k]);

```
				}
```
```
			}
```
```
		//for (int i=0;i<n;i++,puts(""))
```

		//	for (int j=0;j<n;j++) cout<<a[i][j]<<' ';

```
		cout<<dp[0][n-1]<<'\n';
```
```
	}
```
```
	return 0;
```
```
}
```

发表评论取消回复