QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300068#7906. Almost Convexdefyers#WA 10ms3884kbC++172.4kb2024-01-07 17:10:092024-01-07 17:10:10

Judging History

你现在查看的是最新测评结果

  • [2024-01-07 17:10:10]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:3884kb
  • [2024-01-07 17:10:09]
  • 提交

answer

#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) (a).size()
#define forn(i, n) for(int i = 0; i < (n); i++)
#define int long long
using namespace std;

typedef long long ll;
typedef long double LD;
struct P{
    int x, y, id;
    bool operator< (P p) const { return tie(x, y) < tie(p.x, p.y); }
    bool operator== (const P& o) const { return x == o.x && y == o.y; }
    P operator+ (P p) const { return {x + p.x, y + p.y}; }
    P operator- (P p) const { return {x - p.x, y - p.y}; }
    int cross(P p) const { return x * p.y - y * p.x; }
    int dot(P p) const { return x * p.x + y * p.y; }
    int cross(P a, P b) const { return (a - *this).cross(b - *this); }
    int dist2() const { return x * x + y * y; }
    LD dist() const { return sqrt((LD) dist2()); }
};

vector<P> convexHull(vector<P> pts) {
    if(sz(pts) <= 1) return pts;
    sort(all(pts));
    vector<P> h(sz(pts)+1);
    int s = 0, t = 0;
    for (int it = 2; it--; s = --t, reverse(all(pts)))
        for (P p : pts) {
            while(t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
            h[t++] = p;
        }
    return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
}

const int N = 2e3 + 11;
bool not_in[N];

LD angle(P a, P b, P c){
    return abs((a - b).cross(b - c) / (b - c).dist());
}

void solve(){
    int n; cin >> n;
    vector<P> a;
    for(int i = 0; i < n; i++){
        int x, y; cin >> x >> y;
        a.push_back({x, y, i});
    }
    vector<P> C = convexHull(a);
    for(auto [x, y, id] : C){
        not_in[id] = true;
    }
    vector<int> in;
    for(int i = 0; i < n; i++){
        if(!not_in[i]) in.push_back(i);
    }

    int ans = 1;
    for(int i = 0; i < sz(C); i++){
        P A = C[i], B = C[(i + 1) % sz(C)];
        vector<pair<LD, LD>> angles;
        for(auto x : in){
            angles.push_back({angle(A, B, a[x]), angle(B, A, a[x])});
        }
        // for(auto [a, b] : angles) cout << a << ' ' << b << '\n';
        sort(angles.begin(), angles.end());
        LD cur_min = 1 << 30;
        for(auto [x, y] : angles){
            if(y < cur_min)
                ans++;
            cur_min = min(cur_min, y);
        }
    }
    cout << ans << '\n';
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(false);
    int t = 1; // cin >> t;
    while(t--){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

5
4 0
0 0
2 1
3 3
3 1

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

6
0 0
3 0
3 2
0 2
1 1
2 1

output:

7

result:

ok 1 number(s): "7"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Wrong Answer
time: 10ms
memory: 3884kb

input:

2000
86166 617851
383354 -277127
844986 386868
-577988 453392
-341125 -386775
-543914 -210860
-429613 606701
-343534 893727
841399 339305
446761 -327040
-218558 -907983
787284 361823
950395 287044
-351577 -843823
-198755 138512
-306560 -483261
-487474 -857400
885637 -240518
-297576 603522
-748283 33...

output:

102

result:

wrong answer 1st numbers differ - expected: '718', found: '102'