P3433 [POI2005]PRA-Dextrogyrate Camel

#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;
}