QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#299896 | #7906. Almost Convex | kiwiHM# | WA | 1ms | 3872kb | C++14 | 2.1kb | 2024-01-07 13:12:26 | 2024-01-07 13:12:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
int n;
int st[N],top;
struct node{
int x,y;
bool is;
node(){}
node(int xx, int yy, bool iiss){
x = xx;
y = yy;
is = iiss;
}
}p[N],q[N];
node operator - (node a,node b){
return node(a.x - b.x, a.y - b.y, a.is);
}
bool cmp1(node a, node b){
if(a.x != b.x) return a.x < b.x;
else return a.y < b.y;
}
int get(node a){
if(a.y > 0 && a.x >= 0) return 1;
if(a.x > 0 && a.y <= 0) return 2;
if(a.x <= 0 && a.y < 0) return 3;
if(a.y >= 0 && a.x < 0) return 4;
}
bool cmp2(node a,node b){
if(get(a) != get(b)) return get(a) < get(b);
return 1LL * a.y * b.x - 1LL * b.y * a.x > 0;
}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d %d",&p[i].x,&p[i].y);
p[i].is = 0;
}
sort(p + 1, p + 1 + n, cmp1);
st[top = 1] = 1;
for(int i = 2; i <= n; i++){
while(top > 1 && 1LL * (p[i].y - p[st[top - 1]].y) * (p[st[top]].x - p[st[top - 1]].x) >= 1LL * (p[st[top]].y - p[st[top - 1]].y) * (p[i].x - p[st[top - 1]].x)) top--;
st[++top] = i;
}
for(int i = 1; i < top; i++) p[st[i]].is = 1;
st[top = 1] = n;
for(int i = n - 1; i >= 1; i--){
while(top > 1 && 1LL * (p[i].y - p[st[top - 1]].y) * (p[st[top]].x - p[st[top - 1]].x) >= 1LL * (p[st[top]].y - p[st[top - 1]].y) * (p[i].x - p[st[top - 1]].x)) top--;
st[++top] = i;
}
for(int i = 1; i < top; i++) p[st[i]].is = 1;
int ans = 1;
for(int i = 1; i <= n; i++){
if(p[i].is) continue;
int tmp = 0;
for(int j = 1; j <= n; j++){
if(i == j) continue;
q[tmp++] = p[j] - p[i];
}
sort(q, q + n ,cmp2);
int s = 0;
bool flag = 0;
while(q[s].is == 0) s++;
for(int j = (s + 1) % n;; j = (j + 1) % n){
if(q[j].is){
ans += (flag == 0);
flag = 0;
}
else flag = 1;
if(j == s) break;
}
}
printf("%d",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3872kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
8
result:
wrong answer 1st numbers differ - expected: '9', found: '8'