QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333241 | #7906. Almost Convex | JohnAlfnov | WA | 0ms | 3992kb | C++14 | 1.4kb | 2024-02-19 19:05:45 | 2024-02-19 19:05:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int x[2005],y[2005];
long long cha(int a,int b,int c){
return 1ll*(x[b]-x[a])*(y[c]-y[b])-1ll*(y[b]-y[a])*(x[c]-x[b]);
}
long long dian(int a,int b,int c){
return 1ll*(x[b]-x[a])*(x[c]-x[a])+1ll*(y[b]-y[a])*(y[c]-y[a]);
}
int p[2005];
int st[2005];
int vist[2005];
struct apple{
double a1,a2;
bool operator<(const apple &other)const{
if(a1==other.a1)return a2<other.a2;
return a1<other.a1;
}
}e[2005];
double dis(int a,int b){
return sqrt(1.0*(x[a]-x[b])*(x[a]-x[b])+1.0*(y[a]-y[b])*(y[a]-y[b]));
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]),p[i]=i;
sort(p+1,p+n+1,[&](int a,int b){
if(x[a]==x[b])return y[a]<y[b];
return x[a]<x[b];
});
int tt=0;
st[++tt]=p[1];
for(int i=2;i<=n;++i){
while(tt>1&&cha(st[tt-1],st[tt],p[i])<=0)--tt;
st[++tt]=p[i];
}
int t2=tt;
for(int i=n-1;i>=1;--i){
while(tt>t2&&cha(st[tt-1],st[tt],p[i])<=0)--tt;
st[++tt]=p[i];
}
for(int i=1;i<tt;++i)vist[st[i]]=1;
int ans=1;
for(int i=1;i<tt;++i){
int s=0;
for(int j=1;j<=n;++j)if(!vist[j]){
++s;
e[s].a1=dian(st[i],st[i+1],j)/dis(st[i],j);
e[s].a2=dian(st[i+1],st[i],j)/dis(st[i+1],j);
if(i==1&&(j==3||j==4))cout<<e[s].a1<<" "<<e[s].a2<<endl;
}
sort(e+1,e+s+1);
double mx=-1e18;
for(int i=s;i>=1;--i){
if(e[i].a2>=mx)++ans;
mx=max(mx,e[i].a2);
}
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3992kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
2.2188 2.2188 3.79473 2.82843 9
result:
wrong output format Expected integer, but "2.2188" found