oj.uz

Submission #375276

# Submission time Handle Problem Language Result Execution time Memory
375276 2021-03-09T06:02:29 Z Nordway Planine (COCI21_planine) C++14
0 / 110
 22 ms 3692 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define nl '\n'

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;

const int N=1e6+11;
const int M=1e6+1;
const ll inf=1e9+11;
const ld EPS=1e-6;
const ll INF=1e18;
const ll mod=/*999999001*/1e9+7;
const int dx[4]={1,2,2,-1};
const int dy[4]={2,1,-1,2};

struct line{
  ld a,b;
};

line create(int xi,int yi,int xj,int yj){
  ld dx=xi-xj,dy=yi-yj;
  line l;
  l.a=dy/dx;
  l.b=yi-l.a*xi;
  return l;
}

ld get(line l,int y){
  return (y-l.b)/l.a;
}

int x[N],y[N];
pair<ld,ld>l[N];

void solve(){
  int n,h;
  cin>>n>>h;
  for(int i=1;i<=n;i++){
    cin>>x[i]>>y[i];
  }
  for(int i=3;i<n;i+=2){
    line l1=create(x[i],y[i],x[i-1],y[i-1]);
    line l2=create(x[i+1],y[i+1],x[i],y[i]);
    l[(i-1)/2].x=get(l1,h);
    l[(i-1)/2].y=get(l2,h);
    //cout<<l[i]<<" "<<r[i]<<endl;
  }
  n=(n-1)/2;
  n--;
  sort(l+1,l+n+1);
  ld L=l[1].x,R=l[1].y;
  int ans=1;
  for(int i=2;i<=n;i++){
    if(l[i].y<L||l[i].x>R){
      ans++;
      L=l[i].x;
      R=l[i].y;
    }
    else{
      L=max(L,l[i].x);
      R=min(R,l[i].y);
    }
  }
  cout<<ans;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  int T=1;
  //cin>>T;
  for(int i=1;i<=T;i++){
    solve();
    cout<<nl;
  }
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Incorrect 22 ms 3692 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 5 ms 748 KB Output is correct
3 Correct 5 ms 748 KB Output is correct
4 Incorrect 22 ms 3692 KB Output isn't correct
5 Halted 0 ms 0 KB -