P3433 [POI2005]PRA-Dextrogyrate Camel
题目链接：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 希望知道最多能访问多少关键点。
nleq 10^3, |x_i|,|y_i|leq 2times 10^4。
Tutorial
先对所有点以 1 号点为原点进行极角排序。
设 f[i][j] 表示当前位于 i，上一个点为 j 的最大点数，转移时枚举下一个点 k 进行转移。
容易证明能够转移的充要条件是 jrightarrow i rightarrow k 为顺时针旋转，且 1rightarrow irightarrow k 也为顺时针旋转（为了避免两线相交）。
直接暴力枚举转移，时间复杂度 O(N^3)。
但因为常数很小，所以足以通过本题。
Solution
代码语言：javascript复制#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 '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;
}
