oj.uz

Submission #1042319

# Submission time Handle Problem Language Result Execution time Memory
1042319 2024-08-02T20:56:19 Z Alaa7700 Planine (COCI21_planine) C++17
0 / 110
 34 ms 10072 KB 
#include <bits/stdc++.h>

using namespace std;
#define pb push_back

template <typename T>
struct TPoint {
  T x;
  T y;
  int id;

  TPoint() : x(0), y(0), id(-1) {}
  TPoint(const T& x_, const T& y_) : x(x_), y(y_), id(-1) {}
  TPoint(const T& x_, const T& y_, int id_) : x(x_), y(y_), id(id_) {}

};

using point = TPoint<long long>;
//using point = TPoint<long double>;
 

void solve(){
  int n, ans = 0; 
  long long h;
  cin >> n >> h;
  vector<point> p(n);
  int v[n];
  for(int i = 0; i < n; i++){
    cin >> p[i].x >> p[i].y;
    v[i] = 0;
  }
  vector<int> que;
  vector<pair<long double, int> > q;
  for(int i = 2; i < n-2; i +=2){
    long double m = (long double)(p[i-1].y - p[i].y)/(p[i-1].x - p[i].x), c = p[i].y - p[i].x*m;
    q.pb({(h-c)/m, n-i});
    m = (long double)(p[i+1].y - p[i].y)/(p[i+1].x - p[i].x), c = p[i].y - p[i].x*m;
    q.pb({(h-c)/m, n-i});
  }
  int m = q.size();
  sort(q.begin(), q.end());
  for(int i = 0; i < m; i++){
    if(v[n-q[i].second] == 0){
      que.pb(n-q[i].second);
      v[n-q[i].second] ++;
    }else if(v[n-q[i].second] == 1){
      ans ++;
      int l = que.size();
      for(int j = l-1; j >= 0; j--){
        v[que[j]] = 2;
        que.pop_back();
      }
    }
  }
  cout << ans << "\n";
  return;
}

int main() {
  int tt = 1;
  //cin >> tt;
  while(tt--){
      solve();
    } 
  return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1240 KB Output is correct
2 Correct 4 ms 1464 KB Output is correct
3 Correct 4 ms 1496 KB Output is correct
4 Incorrect 34 ms 10072 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 600 KB Output is correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1240 KB Output is correct
2 Correct 4 ms 1464 KB Output is correct
3 Correct 4 ms 1496 KB Output is correct
4 Incorrect 34 ms 10072 KB Output isn't correct
5 Halted 0 ms 0 KB -