单调栈（序列）分析待补，正好区域赛前可以重温一下。

1 /*  2 ID:esxgx1  3 LANG:C++  4 PROG:B  5 */  6 #include 
     
        7 #include 
      
         8 #include 
       
          9 #include 
        
          10 #include 
         
           11 using namespace std; 12  13 const int maxn = 100007; 14  15  16 const double PI = acos(-1.0); 17  18 typedef pair
          
            po; 19 #define px first 20 #define py second 21 22 const double EPS = 1e-9; 23 inline int sgn(double x){ return x < -EPS ? -1 : x > EPS;} 24 template
           
             T det(const T &x0, const T &y0, const T &x1, const T &y1) { return x0*y1 - x1*y0;} 25 double det(const po &p0, const po &p1) { return det(p0.px, p0.py, p1.px, p1.py);} 26 po operator -(const po &a, const po &b) { return make_pair(a.px - b.px, a.py - b.py);} 27 template
            
              int clkws(const T &p, const T &p1, const T &p2){ return sgn(det(p1 - p, p2 - p));} 28 29 struct obss { 30 po p; 31 int id; 32 } obs[maxn]; 33 34 po bl[maxn]; 35 double ll[maxn], rr[maxn]; 36 37 po st[maxn]; 38 int sttf; 39 40 int cmp(const po &a, const po &b) 41 { 42 return a.px < b.px; 43 } 44 45 int cmp2(const obss &a, const obss &b) 46 { 47 return a.p.px < b.p.px; 48 } 49 50 int main(void) 51 { 52 #ifndef ONLINE_JUDGE 53 freopen("in.txt", "r", stdin); 54 #endif 55 56 int tt; 57 scanf("%d", &tt); 58 for(int t=1; t<=tt; ++t) { 59 int nn; 60 scanf("%d", &nn); 61 for(int i=0; i
             
              0 && st[sttf].py <= bl[att].py) --sttf; 79 while(sttf>1 && clkws(st[sttf-1], st[sttf], bl[att]) >= 0) --sttf; 80 st[++sttf] = bl[att]; 81 82 } 83 while(sttf>1 && clkws(st[sttf-1], st[sttf], obs[i].p) >= 0) --sttf; 84 ll[obs[i].id] = PI - atan2(st[sttf].py - obs[i].p.py, st[sttf].px - obs[i].p.px); 85 //printf("ll[%d] : %f st(%f %f) obs(%f %f)\n", i, ll[i], st[sttf].px, st[sttf].py, obs[i].px, obs[i].py); 86 } 87 88 sttf = 0, att = nn-1; 89 90 for(int i=qq; i--; ) { 91 for(; bl[att].px > obs[i].p.px; --att) { 92 //while(sttf>0 && st[sttf].py <= bl[att].py) --sttf; 93 while(sttf>1 && clkws(st[sttf-1], st[sttf], bl[att]) <= 0) --sttf; 94 st[++sttf]= bl[att]; 95 //printf("bl[%d] : %f %f st[%d](%f %f) obs(%f %f)\n", att, bl[att].px, bl[att].py, rr[i], sttf, st[sttf].px, st[sttf].py, obs[i].px, obs[i].py); 96 } 97 while(sttf>1 && clkws(st[sttf-1], st[sttf], obs[i].p) <= 0) --sttf; 98 rr[obs[i].id] = atan2(st[sttf].py - obs[i].p.py, st[sttf].px - obs[i].p.px); 99 //printf("rr[%d] : %f st[%d](%f %f) obs(%f %f)\n", i, rr[i], sttf, st[sttf].px, st[sttf].py, obs[i].px, obs[i].py);100 }101 printf("Case #%d:\n", t);102 for(int i=0; i
             
            
           
          
         
        
       
      
     

 

2014-09-28 01:27:10

Accepted

718MS

7364K

3167 B

G++