#include #include #include #include #include typedef std::pair point; #define px first #define py second #define MAX_N 50 #define MAX_M (MAX_N*MAX_N) // input int N; point loc[MAX_N]; bool edges[MAX_N][MAX_N]; // output int K; int L[MAX_M]; int tour[MAX_M][MAX_N+1]; // triangle area int area2(point a, point b, point c){ return a.px*(b.py-c.py)+ b.px*(c.py-a.py)+ c.px*(a.py-b.py); } // does ab intersect cd? bool intersects(point a, point b, point c, point d){ int a1=area2(a, c, b); int a2=area2(c, b, d); int a3=area2(b, d, a); int a4=area2(d, a, c); // nothing is collinear, no need to check 0 cases return (a1>0 && a2>0 && a3>0 && a4>0) || (a1<0 && a2<0 && a3<0 && a4<0); } bool intersects(int a, int b, int c, int d){ return intersects(loc[a], loc[b], loc[c], loc[d]); } // read the input void read(){ scanf("%d", &N); for(int i=0; i best; // from each starting point, perform multiple random walks, // and pick the longest path for(int start=0; start route; route.push_back(start); mark[start]=true; int at=start; // random walk while(true){ std::random_shuffle(order, order+N); bool found=false; for(int i=0; i2 && edges[at][start]){ bool bad=false; for(int j=1; j<(int)route.size()-2; j++){ if(intersects(route[j], route[j+1], at, start)){ bad=true; break; } } if(!bad){ route.push_back(start); } } // update best route if(route.size() > best.size()) best=route; } // check if we're done if(best.size()==1) break; // add the route to the solution, and erase the corresponding roads for(int i=0; i