【留坑】模拟+极角排序+预处理——ICPC PNWRC 2019 H

/*
两两枚举起始的点，然后按题意模拟寻找下去，为了加速，预处理nxt[i][j]表示直线p[i]->p[j]旋转时，下一个碰到点的下标
 
*/
#include 
#include 
#include 
#include using namespace std ;
const double PI = 3.14159265358979 ;
double fixang(double a) {
   if (a 0)a += PI ;
   if (a > PI)a -= PI ;
   return a ;
}
int main(int argc, char *argv[]) {
   int n ;
   cin >> n ;
   vectordouble> x(n), y(n) ;
   for (int i=0; i)
      cin >> x[i] >> y[i] ;
   vectordouble, int>> sortme ;
   vectorint>> next ;
   vectordouble>> angs ;
   
   for (int i=0; i) {
      sortme.clear() ;
      for (int j=0; j)
         if (i != j) {
            double dy = y[j] - y[i] ;
            double dx = x[j] - x[i] ;
            if (dy 0 || (dy == 0 && dx 0)) {
               dy = - dy ;
               dx = - dx ;
            }
            sortme.push_back({atan2(dy, dx),j}) ;
         }
      sort(sortme.begin(), sortme.end()) ;
      vectorint> v(n) ;
      vectordouble> ang(n) ;
      //处理首位衔接 
      v[sortme[sortme.size()-1].second] = sortme[0].second ;
      ang[sortme[sortme.size()-1].second] =
                     fixang(sortme[0].first - sortme[sortme.size()-1].first) ;
      
      //以i为中点时的下一个点 
      for (int j=0; j+1int)sortme.size(); j++) {
         v[sortme[j].second] = sortme[j+1].second ;
         ang[sortme[j].second] = fixang(sortme[j+1].first - sortme[j].first) ;
      }
      
      next.push_back(v) ;
      angs.push_back(ang) ;
   }
   
   vectorchar> > seen ;
   for (int i=0; i)
      seen.push_back(vectorchar>(n)) ;
   
   int r = 0 ;
   for (int i=0; i)
      for (int j=0; j)
         if (i != j && !seen[i][j]) {//两两枚举起始直线(未被访问过的) 
            vectorint> cnts(n) ;
            int ii = i ;
            int jj = j ;
            double totspin = 0 ;
            while (1) {
               cnts[ii]++ ;
               seen[ii][jj] = 1 ;
               int kk = next[ii][jj] ;//不停找下一个点，构成新的直线 
               totspin += angs[ii][jj] ;//累加转过的角度 
               jj = ii ;
               ii = kk ;
               if (ii == i && jj == j && totspin >= 1.5 * PI)//重新回到原来的点 
                  break ;
            }
            for (auto v : cnts)
               r = max(r, v) ;
         }
   cout  endl ;
}