QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314187#7906. Almost ConvexhazeTL 0ms4124kbC++233.6kb2024-01-25 14:02:532024-01-25 14:02:53

Judging History

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

  • [2024-01-25 14:02:53]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4124kb
  • [2024-01-25 14:02:53]
  • 提交

answer

/*

Author: Haze

2024/1/24

*/

#include <bits/stdc++.h>

#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;

inline ll read() {
    ll s = 0;
    bool fl = false;
    char ch = (char) getchar();
    while (!isdigit(ch)) {
        if (ch == '-')fl = true;
        ch = (char) getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + (ch ^ 48);
        ch = (char) getchar();
    }
    return fl ? -s : s;
}

#define LD long long

struct point{
    LD x, y;
    point(){}
    point(LD _X,LD _Y) : x(_X), y(_Y){}
    LD operator *(const point &A)const {
        return x * A.x + y * A.y;
    }
    LD operator ^(const point &A)const{
        return x * A.y - y * A.x;
    }
    point operator +(const point &A)const {
        return point(x + A.x, y + A.y);
    }
    point operator -(const point &A)const {
        return point(x - A.x, y - A.y);
    }
    double len(){
        return sqrt(x * x + y * y);
    }
    bool operator ==(const point &A)const {
        return A.x == x && A.y == y;
    }
};

const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
const double eps = 1e-8;
int sgn(double X){
    if(X > eps)return 1;
    if(X < -eps)return -1;
    return 0;
}

bool turn_left(point A, point B, point C){
    return sgn((B - A) ^ (C - A)) < 0;
}

void convex_hull (vector<point> a, vector<point> &ret){
    if(a.size() <= 2)return;
    sort(a.begin(), a.end(), [](const point &A, const point &B){
        return A.x == B.x ? A.y > B.y : A.x < B.x;
    });
    int n = a.size();
    irep(i, 0, n - 1){
        while(ret.size() > 1 && 
        ! turn_left(*(ret.end() - 2), *(ret.end() - 1), a[i]))
            ret.pop_back();
        ret.push_back(a[i]);
    }
    int fixed = (int)ret.size();
    drep(i, n - 2, 0){
        while(ret.size() > fixed && 
        ! turn_left(*(ret.end() - 2), *(ret.end() - 1), a[i]))
            ret.pop_back();
        ret.push_back(a[i]);
    }
    
    ret.pop_back();
    return;
}

void solve() {
    int n = read();
    vector<point>a(n), con, ins;
    vector<int>tp(n), ord(n);
    //convex -> 1, inside -> 0
    irep(i, 0, n - 1){
        ll x = read(), y = read();
        a[i] = point(x, y);
    }
    convex_hull(a, con);
    int m = con.size();
    ll ans = 1;
    irep(i, 0, n - 1){
        bool fl = 0;
        irep(j, 0, m - 1){
            if(a[i] == con[j]){
                fl = 1;
                break;
            }
        }
        if(! fl)
            ins.push_back(a[i]);
        tp[i] = fl;
    }
    irep(i, 0, n - 1)ord[i] = i;
    for(int i = 0; i < ins.size(); ++ i){
        sort(ord.begin(), ord.end(), [&](int I, int J){
            point A = a[I] - ins[i], B = a[J] - ins[i];
            if(A == point(0, 0))return false;
            if(B == point(0, 0))return true;
            //UU < 0 0
            return atan2(A.x, A.y) < atan2(B.x, B.y);
        });
        /*
        cerr << "i = " << i << endl;
        cerr << a[i].x << ' ' << a[i].y << '\n' << '\n';
        irep(j, 0, n - 1){
            cerr << a[ord[j]].x << ' ' << a[ord[j]].y << endl;
        }
        cerr << endl;
        */
        for(int j = 0; j < n - 1; ++ j){
            if(tp[ord[j]] == 1 && tp[ord[(j + 1) % (n - 1)]] == 1)
                ++ ans;
        }
    }
    cout << ans;
}

int main() {
    // IOS
    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4020kb

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: 3944kb

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: 3600kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

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: 3728kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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:


result: