#include using namespace std; typedef signed long long ll; #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define FORR2(x,y,arr) for(auto& [x,y]:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) template bool chmax(T &a, const T &b) { if(a bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;} //------------------------------------------------------- int N; ll X[2010],Y[2010]; int cross(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4) { ll XX[3],YY[3]; XX[0]=x2-x1; YY[0]=y2-y1; XX[1]=x3-x1; YY[1]=y3-y1; XX[2]=x4-x1; YY[2]=y4-y1; //bounding box判定。同一直線上に並ぶケースを除外 if(max(x1,x2)0&&c2>0)) return 0; XX[0]=x4-x3; YY[0]=y4-y3; XX[1]=x1-x3; YY[1]=y1-y3; XX[2]=x2-x3; YY[2]=y2-y3; c1=XX[0]*YY[1]-XX[1]*YY[0]; c2=XX[0]*YY[2]-XX[2]*YY[0]; if((c1<0&&c2<0)||(c1>0&&c2>0)) return 0; return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>X[i]>>Y[i]; X[N+i]=X[i]; Y[N+i]=Y[i]; } // 隣以外で交差したらアウト FOR(x,N) for(y=x+2;y