Submission #375276

#	Time	Username	Problem	Language	Result	Execution time	Memory
375276		Nordway	Planine (COCI21_planine)	C++14	0 / 110	22 ms	3692 KiB

Main

#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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60