QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413576#7906. Almost Convexgrass8cow#WA 1ms3764kbC++171.4kb2024-05-17 19:23:382024-05-17 19:23:39

Judging History

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

  • [2024-05-17 19:23:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2024-05-17 19:23:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n;
#define ll long long
struct no{ll x,y;int id;
inline int hf(){
    return x>0||x==0&&y>0;
}
};
no operator - (const no &a,const no &b){return (no){a.x-b.x,a.y-b.y,0};}
ll cro(no a,no b){return a.x*b.y-a.y*b.x;}
no s[4010],a[4010];
int tp;
#define pb push_back
bool vis[4010];
int main(){
    scanf("%d",&n);ll x_,y_;
    for(int i=1;i<=n;i++)scanf("%lld%lld",&x_,&y_),a[i]=(no){x_,y_},a[i].id=i;
    sort(a+1,a+n+1,[&](no a,no b){if(a.x!=b.x)return a.x<b.x;return a.y<b.y;});
    for(int i=1;i<=n;i++){
        while(tp>1&&cro(s[tp]-s[tp-1],a[i]-s[tp])<0)tp--;
        s[++tp]=a[i];
    }
    int kt=tp;
    for(int i=n-1;i;i--){
        while(tp>kt&&cro(s[tp]-s[tp-1],a[i]-s[tp])<=0)tp--;
        s[++tp]=a[i];
    }
    for(int i=1;i<tp;i++)vis[s[i].id]=1;
    int ans=1;
    for(int i=1;i<=n;i++)if(!vis[i]){
        vector<no>cs;
        for(int j=1;j<tp;j++){
            no cx=s[j]-a[i];cx.id=1;
            cs.pb(cx);
        }
        for(int j=1;j<=n;j++)if(i!=j&&!vis[j])
        cs.pb(s[j]-a[i]);
        sort(cs.begin(),cs.end(),[&](no a,no b){if(a.hf()!=b.hf())return a.hf()<b.hf();return cro(a,b)>0;});
        int sz=cs.size(),fi=-1,lst=-1;
        for(int j=0;j+1<sz;j++)if(cs[j].id&&cs[j+1].id)ans++;
        if(cs[0].id&&cs[sz-1].id)ans++;
    }
    return printf("%d",ans),0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3764kb

input:

7
1 4
4 0
2 3
3 1
3 5
0 0
2 4

output:

7

result:

wrong answer 1st numbers differ - expected: '9', found: '7'