P3433 [POI2005]PRA-Dextrogyrate Camel

(Updated: )
oi

题目链接：P3433

小 $\mathrm{H}$ 听说在 $n$ 个不同的地方分别降下了雪，非常激动，于是约小 $\mathrm{S}$ 一起去赏雪。
小 $\mathrm{S}$ 平时习惯利用虫洞进行空间穿梭，并不是很想走路，但看着小 $\mathrm{H}$ 兴奋的样子，还是答应了。
地面可以视作一个二维平面，小 $S$ 观测到第 $i$ 个降下了雪的地方 (以下简称为关键点) 的坐标为 $\left(x_{i}, y_{i}\right)_{\text {。非常巧 }}$ 合的是，小 $\mathrm{H}$ 恰好位于 1 号关键点，小 $\mathrm{S}$ 恰好位于 2 号关键点。
小 $\mathrm{H}$ 会先从自己所在的 1 号点走向小 $S$ 所在的 2 号点，然后和小 $S$ 一起去若干关键点赏雪。不过由于小 $S$ 并没有 去过小 $\mathrm{H}$ 最初的位置，所以最后她们会一起走回 1 号点。
根据各自的需要，她们为这趟赏雪之旅制定了两个规则：

  • 因为小 S 不想走太多路，所以她们 只会在关键点转换方向，而且转换方向时只能向 顺时针方向旋转 $\left(0^{\circ}, 180^{\circ}\right)$ 范围内的一个角度。
  • 因为小 $\mathrm{H}$ 觉得重复经过同一个地方很没意思，所以她们走过的路线 无交。
    为了防止产生歧义，这里再做出一些细节方面的补充说明/提示:
  • 小 $H$ 从 1 号点走到 2 号点并转换方向的过程中虽然小 S 并不参与，但还是需要满足小 S 给出的条件。
  • 走回 1 号点之后她们的赏雪之旅就结束了，因此最后走回 1 号点的线段和最初离开 1 号点的线段的夹角并没 有限制。
  • 路线无交指的是她们依次经过的所有关键点之间的连线，除了起点和终点都是 1 号点外，不在任何地方（包 括关键点和非关键点）重复。

小 H 和小 S 希望知道最多能访问多少关键点。

$n\leq 10^3, |x_i|,|y_i|\leq 2\times 10^4$。

Tutorial

先对所有点以 $1$ 号点为原点进行极角排序。

设 $f[i][j]$ 表示当前位于 $i$，上一个点为 $j$ 的最大点数，转移时枚举下一个点 $k$ 进行转移。

容易证明能够转移的充要条件是 $j\rightarrow i \rightarrow k$ 为顺时针旋转，且 $1\rightarrow i\rightarrow k$ 也为顺时针旋转（为了避免两线相交）。

直接暴力枚举转移，时间复杂度 $O(N^3)$。

但因为常数很小，所以足以通过本题。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e3+10,inf=2e9;Cn double Pi=3.14159265359;
int n,f[N][N],Ans;
struct node{int x,y,id;}a[N];
I bool cmp(Cn node& x,Cn node& y){return atan2(x.y,x.x)>atan2(y.y,y.x);}
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second 
I bool Turn(CI i,CI j,CI k){
	pa v1=mp(a[j].x-a[i].x,a[j].y-a[i].y),v2=mp(a[k].x-a[j].x,a[k].y-a[j].y);
	swap(v1.fi,v1.se),v1.se=-v1.se;
	return v1.fi*v2.fi+v1.se*v2.se>0; 
}
int main(){
	RI i,j,k,st=-1;for(read(n),i=0;i<n;i++) read(a[i].x,a[i].y),a[i].id=i;
	for(i=1;i<n;i++) a[i].x-=a[0].x,a[i].y-=a[0].y;
	for(a[0].x=a[0].y=0,sort(a+1,a+n,cmp),i=0;i<n;i++) a[i].id==1&&(st=i);
	for(i=1;i<st;i++) a[i-1]=a[i];a[st-1].x=a[st-1].y=a[st-1].id=0;
	for(i=0;i<n;i++) for(j=0;j<n;j++) f[i][j]=-inf;
	assert(~st);for(i=1;i<n-1;i++) assert(a[(st+n-1)%n].id==0),Turn((st+n-1)%n,st,(st+i)%n)&&(/*gdb(st,i),*/f[i][0]=2);
	for(i=0;i<n;i++) for(k=i+1;k<n;k++) if((k==n-1||Turn((st+n-1)%n,(st+i)%n,(st+k)%n))) for(j=0;j<i;j++) 
		if(f[k][i]<f[i][j]+1&&Turn((st+j)%n,(st+i)%n,(st+k)%n)) f[k][i]=f[i][j]+1;
	for(j=1;j<n-1;j++) Ans=max(Ans,f[n-1][j]);
	return writeln(Ans),0;
}