QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299896#7906. Almost ConvexkiwiHM#WA 1ms3872kbC++142.1kb2024-01-07 13:12:262024-01-07 13:12:26

Judging History

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

  • [2024-01-07 13:12:26]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3872kb
  • [2024-01-07 13:12:26]
  • 提交

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'