POJ 1208 极角序-白红宇

POJ 1208 极角序

阅读量：6406 次

发布时间：2019-06-23

本文共 1277 字，大约阅读时间需要 4 分钟。

//Result:wizmann	1228	Accepted	268K	79MS	C++	2943B#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define print(x) cout<
             
              <
              
               >x#define SIZE 1024const double inf=1e100;const double eps=1e-8;inline int zero(double x){ if(x<-eps) return -1; else if(fabs(x)
               
                0; }};int n;point polygen[SIZE];int findtop(){ int res=0; for(int i=0;i
                
                  visit; int edge=0; visit.reset(); for(int i=0;i
                 
                   inque; int now=i; line l=makeline(polygen[now],polygen[(now+1)%n]); deque
                  
                    dq; dq.push_back(now); int ptr=now+1; while(1) { if(!inque[ptr] && zero(l.a*polygen[ptr].x+l.b*polygen[ptr].y+l.c)==0) { inque[ptr]=1; dq.push_back(ptr); ptr=(ptr+1)%n; } else break; } ptr=(now-1+n)%n; while(1) { if(!inque[ptr] && zero(l.a*polygen[ptr].x+l.b*polygen[ptr].y+l.c)==0) { inque[ptr]=1; dq.push_front(ptr); ptr=(ptr-1+n)%n; } else break; } //print(dq.size()); if(dq.size()<3) return false; else { edge++; dq.pop_front(); dq.pop_back(); for(int j=0;j<(int)dq.size();j++) visit[dq[j]]=1; } } return edge>=3;} int main(){ int T; double a,b; input(T); while(T--) { input(n); for(int i=0;i