QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431644#7894. Many Many HeadsBotterWA 0ms3688kbC++142.1kb2024-06-05 20:49:352024-06-05 20:49:36

Judging History

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

  • [2024-06-05 20:49:36]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3688kb
  • [2024-06-05 20:49:35]
  • 提交

answer

//
// Created by Botter on 2024/6/5.
//

#include <bits/stdc++.h>

using namespace std;
const long long N = 2005;
struct point{
    long long x,y;
}s[N],p[N],yu[N];
long long n,st[N],top,res[N];
bool vis[N],vis1[N];
bool cmp(const point a , const point b){
    if (a.y == b.y){
        return a.x<b.x;
    }
    return a.y < b.y;
}
bool mult(point a,point b,point c){
    return (a.x-c.x) *(b.y-c.y) >= (b.x-c.x)*(a.y-c.y);
}
long long corss(point a,point b,point c){
    return abs((a.x-c.x) *(b.y-c.y) - (b.x-c.x)*(a.y-c.y));
}
bool sing(point a,point b ,point c,point p){
    long long S =corss(a,b,c);
    long long s1=corss(a,b,p);
    long long s2=corss(a,c,p);
    long long s3=corss(b,c,p);
    return S == s1+s2+s3;
}
void Se(){
    long long i,len;
    top=1;
    sort(s,s+n,cmp);
    res[1]=1,res[2]=2;
    for (i=2;i<n;++i){
        while (top&&mult(s[i],s[res[top]],s[res[top-1]])) top--;
        res[++top]=i;
    }
    len = top;
    res[++top] = n-2;
    for (i = n-3;i>=0;--i){
        while(top!=len&&mult(s[i],s[res[top]],s[res[top-1]])) top--;
        res[++top]=i;
    }
}
int main() {
    long long ly=0,lb=0;
    long long ans=1;

    ios::sync_with_stdio(0);cin.tie();cout.tie();
    cin >> n;
    if (n == 3) {cout << 1 <<endl; return 0;}
    for (long long i=0;i<n;++i)cin>>s[i].x >> s[i].y;
    Se();
    for (long long i = 0 ; i < top ; ++i){
        p[lb++] = s[res[i]];
        vis[res[i]] = 1;
    }
    for (long long i = 0 ; i < n ; i++){
        if (!vis[i]) yu[ly++] = s[i];
    }
    for (long long i = 0 ; i < lb;++i){
        point a = p[i],b=p[(i+1)%lb];
        for (int j = 0;j<ly;++j){
            point c = yu[j];
            int k = 0;
            long long cnt = 0;
            for ( k = 0 ; k < ly ; ++k){
                if (j == k) continue;
                if (sing(a,b,c,yu[k])) {//有点在三角内
                    break;
                }
                else{
                    cnt++;
                }
            }
            if (cnt == ly-1) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3688kb

input:

6
))
((()
[()]
()[()]()
([()])
([])([])

output:

1

result:

wrong output format YES or NO expected, but 1 found [1st token]