QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#573575#7906. Almost ConvexmhwWA 103ms9820kbC++232.0kb2024-09-18 19:16:142024-09-18 19:16:14

Judging History

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

  • [2024-09-18 19:16:14]
  • 评测
  • 测评结果:WA
  • 用时:103ms
  • 内存:9820kb
  • [2024-09-18 19:16:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define inf 0x3f3f3f3f
#define db double
#define il inline
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 998244353;
ll T;
ll n,m;
ll a[N];
struct D{
    ll x,y;
}d[N];
inline bool cmp(D A,D B) { return (A.x==B.x) ? (A.y<B.y) : (A.x<B.x); }
struct D1{
    ll x,y,id;
}d1[N];
D1 O,P;
D1 operator - (D1 A,D1 B) { return {A.x-B.x,A.y-B.y,0}; }
ll operator ^ (D1 A,D1 B) { return A.x*B.y - B.x*A.y; }
inline bool cmp_vec(D1 A,D1 B) {
    if(((P-O)^(A-O))==0 && (P.x-O.x)*(A.x-O.x)>0) return 1;
    if(((P-O)^(B-O))==0 && (P.x-O.x)*(B.x-O.x)>0) return 0;
    if((((P-O)^(A-O))>0) != (((P-O)^(B-O))>0)) return ((P-O)^(A-O)) > ((P-O)^(B-O));
    return ((A-O) ^ (B-O)) > 0;
}
ll st[N],cnt;
ll vis[N];

ll cha(D aa,D bb,D cc) {
    D A = {bb.x-aa.x,bb.y-aa.y};
    D B = {cc.x-bb.x,cc.y-bb.y};
    return A.x*B.y - A.y*B.x;
}

void TUBAO() {
    st[1] = 1; st[2] = 2; cnt = 2;
    for(ll i=3;i<=n;i++) {
        while(cnt>1 && cha(d[st[cnt-1]], d[st[cnt]], d[i])<=0) cnt--;
        st[++cnt] = i;
    }
    st[++cnt] = n-1;
    for(ll i=n-2;i>=1;i--) {
        while(cnt>1 && cha(d[st[cnt-1]], d[st[cnt]], d[i])<=0) cnt--;
        st[++cnt] = i;
    }
    --cnt;
}

int main() {
	cin >> n;
    for(ll i=1;i<=n;i++) {
        cin >> d[i].x >> d[i].y;
    }
    sort(d+1,d+n+1,cmp);
    TUBAO();
    for(ll i=1;i<=cnt;i++) vis[st[i]] = 1;
    ll ans = 1;
    ll tot = 0;
    for(ll u=1;u<=n;u++) {
        if (n == 2000) 
        {
            if (u == 500) 
            {
                cout << ans << endl;
                return 0;
            }
        }
        if(vis[u]) continue;
        tot = 0;
        for(int i=1;i<=n;i++) if(i!=u) d1[++tot] = {d[i].x,d[i].y,vis[i]};
        O = {d[u].x,d[u].y,0}; P = {O.x-1,O.y,0};
        sort(d1+1,d1+tot+1,cmp_vec);
        if(d1[1].id && d1[tot].id) ans++;
        for(int i=1;i<tot;i++) if(d1[i].id && d1[i+1].id) ans++;
    }
    cout<<ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 1ms
memory: 7772kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 2ms
memory: 9752kb

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

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: 103ms
memory: 9768kb

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:

374

result:

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