QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#413576 | #7906. Almost Convex | grass8cow# | WA | 1ms | 3764kb | C++17 | 1.4kb | 2024-05-17 19:23:38 | 2024-05-17 19:23:39 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'