fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. typedef long long ll;
  5. const ll INF = 100000000000ll;
  6.  
  7. #define N 100010
  8. struct point{
  9.     ll x, y;
  10.     point(ll x=0, ll y=0): x(x), y(y){}
  11.     point operator -(const point &b) const{
  12.         return point(x-b.x, y-b.y);
  13.     }
  14.     ll operator %(const point &b) const{
  15.         return x*b.y-y*b.x;
  16.     }
  17. };
  18. point yama[N];
  19. int st[N], chl[N], chr[N];
  20. struct frac{
  21.     ll p, q;
  22.     frac(ll p=0, ll q=1): p(p), q(q){}
  23.     bool operator <(const frac &b) const{
  24.         return p*b.q < q*b.p;
  25.     }
  26. };
  27. pair<frac, frac> kukan[N];
  28.  
  29. #define M 100010
  30. frac b[M];
  31.  
  32. int main(){
  33.     int n;
  34.     while(scanf("%d", &n) == 1){
  35.         for(int i=1; i<=n; i++){
  36.             scanf("%lld%lld", &yama[i].x, &yama[i].y);
  37.         }
  38.         int len=1; st[1]=1;
  39.         for(int i=2; i<=n; i++){
  40.             while(len>=2){
  41.                 point u=yama[i]-yama[st[len]], v=yama[st[len]]-yama[st[len-1]];
  42.                 if(u%v > 0) break;
  43.                 len--;
  44.             }
  45.             chl[i] = st[len];
  46.             st[++len] = i;
  47.         }
  48.         len=1; st[1]=n;
  49.         for(int i=n-1; i>=1; i--){
  50.             while(len>=2){
  51.                 point u=yama[i]-yama[st[len]], v=yama[st[len]]-yama[st[len-1]];
  52.                 if(u%v < 0) break;
  53.                 len--;
  54.             }
  55.             chr[i] = st[len];
  56.             st[++len] = i;
  57.         }
  58.         int m;
  59.         ll h;
  60.         scanf("%d%lld", &m, &h);
  61.         kukan[1].second = frac(-INF, 1);
  62.         for(int i=2; i<=n; i++){
  63.             ll x1=yama[i].x, y1=yama[i].y, x2=yama[chl[i]].x, y2=yama[chl[i]].y;
  64.             if(y1 >= y2){
  65.                 kukan[i].second = frac(-INF, 1);
  66.             }else{
  67.                 kukan[i].second = frac(x2*(y2-y1)-(h-y2)*(x1-x2), y2-y1);
  68.             }
  69.         }
  70.         kukan[n].first = frac(INF, 1);
  71.         for(int i=n-1; i>=1; i--){
  72.             ll x1=yama[i].x, y1=yama[i].y, x2=yama[chr[i]].x, y2=yama[chr[i]].y;
  73.             if(y1 >= y2){
  74.                 kukan[i].first = frac(INF, 1);
  75.             }else{
  76.                 kukan[i].first = frac(x2*(y2-y1)-(h-y2)*(x1-x2), y2-y1);
  77.             }
  78.         }
  79.         sort(kukan+1, kukan+n+1);
  80.         for(int i=1; i<=m; i++){
  81.             scanf("%lld", &b[i].p);
  82.             b[i].q = 1;
  83.         }
  84.         int ans = 0;
  85.         bool feasible = true;
  86.         frac loli = frac(-INF, 1);
  87.         for(int i=1, j=1; i<=n; i++){
  88.             if(kukan[i].second < loli){
  89.                 continue;
  90.             }
  91.             while(j<=m && b[j]<kukan[i].first){
  92.                 j++;
  93.             }
  94.             j--;
  95.             if(j==0 || !(kukan[i].second<b[j])){
  96.                 feasible = false; break;
  97.             }
  98.             loli = b[j]; ans++;
  99.         }
  100.         if(feasible){
  101.             printf("%d\n", ans);
  102.         }else{
  103.             puts("you need more bulbs!");
  104.         }
  105.     }
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0s 8988KB
comments (?)
stdin
copy 
6
1 1
3 3
4 1
7 1
8 3
11 1
4 5
1 5 6 10

6
1 1
3 3
4 1
7 1
8 3
11 1
2 5
1 5
stdout
copy 
2
you need more bulbs!
https://ideone.com/z7J87D
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!