QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#573575 | #7906. Almost Convex | mhw | WA | 103ms | 9820kb | C++23 | 2.0kb | 2024-09-18 19:16:14 | 2024-09-18 19:16:14 |
Judging History
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'