HDU 5033

单调栈（序列）分析待补，正好区域赛前可以重温一下。
  1 /*
  2 ID:esxgx1
  3 LANG:C++
  4 PROG:B
  5 */
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <iostream>
  9 #include <algorithm>
 10 #include <cmath>
 11 using namespace std;
 12 
 13 const int maxn = 100007;
 14 
 15 
 16 const double PI = acos(-1.0);
 17 
 18 typedef pair<double, double> 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<typename T> 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<typename T> 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<nn; ++i)
 62             scanf("%lf%lf", &bl[i].px, &bl[i].py);
 63         sort(bl, bl+nn, cmp);
 64 
 65         int qq;
 66         scanf("%d", &qq);
 67         for(int i=0; i<qq; ++i) {
 68             scanf("%lf", &obs[i].p.px);
 69             obs[i].id = i;
 70         }
 71         sort(obs, obs+qq, cmp2);
 72 
 73         int att;
 74 
 75         sttf = 0, att = 0;
 76         for(int i=0; i<qq; ++i) {
 77             for(; bl[att].px < obs[i].p.px; ++att) {
 78                 //while(sttf>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)
", 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)
", 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)
", i, rr[i], sttf, st[sttf].px, st[sttf].py, obs[i].px, obs[i].py);
100         }
101         printf("Case #%d:
", t);
102         for(int i=0; i<qq; ++i)
103             printf("%.9f
", (PI - ll[i] - rr[i])/PI * 180);
104     }
105     return 0;
106 }
2014-09-28 01:27:10
Accepted
5033
718MS
7364K
3167 B
G++