oj.uz

답안 #386509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386509 2021-04-06T17:00:43 Z phathnv Planine (COCI21_planine) C++11
20 / 110
 324 ms 48444 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 7;

struct Point{
    int x, y;
    Point(int _x = 0, int _y = 0){
        x = _x;
        y = _y;
    }
};

struct Line{
    ll a, b, c;
    Line(ll _a, ll _b, ll _c){
        a = _a;
        b = _b;
        c = _c;
    }
    Line(const Point &A, const Point &B){
        a = A.y - B.y;
        b = B.x - A.x;
        c = (ll) A.x * B.y - (ll) A.y * B.x;
    }
};

int n, h;
Point p[N];

long double findXCoor(const Line &d1, const Line &d2){
    ll D = d1.a * d2.b - d2.a * d1.b;
    ll Dx = -d1.c * d2.b + d2.c * d1.b;
    assert(D != 0);
    return (long double) Dx / D;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> h;
    for(int i = 1; i <= n; i++)
        cin >> p[i].x >> p[i].y;

    Line d(0, 1, -h);
    vector<pair<long double, long double>> segments;
    for(int i = 3; i <= n - 2; i += 2){
        //cerr << findXCoor(Line(p[i - 1], p[i]), d) << ' ' << findXCoor(Line(p[i], p[i + 1]), d) << endl;
        segments.push_back({findXCoor(Line(p[i - 1], p[i]), d), findXCoor(Line(p[i], p[i + 1]), d)});
    }
    sort(segments.begin(), segments.end(), [](const pair<long double, long double> &a, const pair<long double, long double> &b){
            if (a.second != b.second)
                return a.second < b.second;
            return a.first > b.first;
         });
    long double lastX = -1e18;
    vector<pair<long double, long double>> nxt;
    for(auto p : segments)
        if (lastX < p.first){
            lastX = p.first;
            nxt.push_back(p);
        }
    sort(nxt.begin(), nxt.end());
    lastX = -1e18;
    int answer = 0;
    for(auto p : nxt)
        if (lastX < p.first){
            answer++;
            lastX = p.second;
        }
    cout << answer;

    return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8556 KB Output is correct
2 Correct 8 ms 8556 KB Output is correct
3 Correct 9 ms 8560 KB Output is correct
4 Correct 34 ms 12772 KB Output is correct
5 Correct 36 ms 12772 KB Output is correct
6 Correct 36 ms 11236 KB Output is correct
7 Correct 282 ms 38872 KB Output is correct
8 Correct 323 ms 48444 KB Output is correct
9 Correct 324 ms 38076 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8172 KB Output is correct
2 Incorrect 6 ms 8300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8556 KB Output is correct
2 Correct 8 ms 8556 KB Output is correct
3 Correct 9 ms 8560 KB Output is correct
4 Correct 34 ms 12772 KB Output is correct
5 Correct 36 ms 12772 KB Output is correct
6 Correct 36 ms 11236 KB Output is correct
7 Correct 282 ms 38872 KB Output is correct
8 Correct 323 ms 48444 KB Output is correct
9 Correct 324 ms 38076 KB Output is correct
10 Correct 6 ms 8172 KB Output is correct
11 Incorrect 6 ms 8300 KB Output isn't correct
12 Halted 0 ms 0 KB -