QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#539 | #332904 | #7906. Almost Convex | wYYSZL | wYYSZL | Failed. | 2024-02-19 18:22:50 | 2024-02-19 18:22:50 |
詳細信息
Extra Test:
Accepted
time: 0ms
memory: 3900kb
input:
3 1 1 2 2 0 3
output:
1
result:
ok 1 number(s): "1"
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#332904 | #7906. Almost Convex | wYYSZL | AC ✓ | 153ms | 4392kb | C++14 | 2.6kb | 2024-02-19 16:25:01 | 2024-02-19 16:25:02 |
answer
#include<bits/stdc++.h>
#define int long long
#define pi (3.1415926)
using namespace std;
int n;
int ans=1;
int x[2005],y[2005];
vector<int>xl;
int maxx=-1e7,maxi;
bool b[2005];
double deg(int a,int b){
auto d=atan2(y[a]-y[b],x[a]-x[b]);
if(d<0)d+=pi;
return d;
}
double todeg(int a,int b,int c){
// cout<<a<<' '<<b<<' '<<c<<'\n';
double A=sqrtl((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])),
B=sqrtl((x[a]-x[c])*(x[a]-x[c])+(y[a]-y[c])*(y[a]-y[c])),
C=sqrtl((x[b]-x[c])*(x[b]-x[c])+(y[b]-y[c])*(y[b]-y[c]));
// cerr<<x[a]-x[b]<<' '<<y[a]-y[b]<<'\n';
// cerr<<A*A<<' '<<B*B<<' '<<C*C<<' '<<(A*A+B*B-C*C)/2/A/B<<'\n';
double ans=acos((A*A+B*B-C*C)/2/A/B);
while(ans<0)ans+=pi;
while(ans>pi)ans-=pi;
// cout<<a<<' '<<b<<' '<<c<<' '<<ans<<'\n';
// cout<<ans<<'\n';
return ans;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
//freopen("1.in","r",stdin);
cin>>n;
for(int i=1;i<=n;++i){
cin>>x[i]>>y[i];
if(y[i]>maxx)
maxx=y[i],maxi=i;
}
double mx=-1e7;int mi=0;
for(int i=1;i<=n;++i){
if(i==maxi)continue;
if(x[i]==x[maxi])continue;
double k=(y[i]-maxx)*1.0/(x[i]-x[maxi]);
double b=y[i]-k*x[i];
// cerr<<k<<' '<<b<<'\n';
int op=0;
int bl=1;
for(int j=1;j<=n;++j){
if(j==i or j==maxi)continue;
if(!op)op=(x[j]*k+b>y[j]?-1:1);
else if(op!=(x[j]*k+b>y[j]?-1:1)){bl=0;break;}
}
if(bl){mi=i;break;}
}
int tp=mi,last=maxi;
int st=maxi;
xl.push_back(maxi);
xl.push_back(mi);
b[tp]=b[maxi]=1;
while(1){
double maxx=-114;
int maxi=0;
for(int i=1;i<=n;++i){
if(b[i])continue;
if(todeg(tp,last,i)>maxx)
maxx=todeg(tp,last,i),maxi=i;
}
if(todeg(tp,last,st)>maxx)break;
last=tp;
tp=maxi;
xl.push_back(tp);
b[tp]=1;
}
// for(auto z:xl)cout<<x[z]<<' '<<y[z]<<'\n';
int sz=xl.size()-1;
for(int i=0;i<=sz;++i)xl.push_back(xl[i]);
// cerr<<"\n-------------------------\n";
for(int i=0;i<=sz;++i){
vector<pair<double,double> >lx={};
// cout<<xl[i]<<' '<<xl[i+1]<<'\n';
for(int j=1;j<=n;++j){
if(b[j])continue;
// cout<<xl[i]<<' '<<xl[i+1]<<'\n';
lx.push_back({todeg(xl[i],xl[i+1],j),\
todeg(xl[i+1],xl[i],j)});
// cout<<todeg(xl[i],xl[i+1],j)<<' '<<todeg(xl[i+1],xl[i],j)<<'\n';
}
sort(lx.begin(),lx.end());
double miny=lx[0].second;
for(int i=0;i<lx.size();++i){
++ans;
if(!i)continue;
// if(lx[i].first>lx[i-1].first and lx[i].second>lx[i-1].second)
// --ans;
if(lx[i].second>miny)--ans;
else miny=min(miny,lx[i].second);
}
// cout<<ans<<' ';
}
cout<<ans<<'\n';
return 0;
}