QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#713954 | #7906. Almost Convex | k1rito | WA | 1ms | 3936kb | C++14 | 2.0kb | 2024-11-05 21:00:18 | 2024-11-05 21:00:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define db double
const int mod=1e9+7;
const int N=2e3+10;
const db PI=acos(-1);
const db eps=1e-14;
int n,tp,s[N],whe[N],T,vis[N],ans,m,now,st[N];
struct V
{
db x,y;
int id;
}a[N],b[N];
db calcompare(db x,db y,db xx,db yy)
{
return x*yy-xx*y;
}
bool cmp(V a,V b)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(V A,V B)
{
V c;
c=a[now];
if(calcompare(A.x-c.x,A.y-c.y,B.x-c.x,B.y-c.y)==0)
return A.x<B.x;
else return calcompare(A.x-c.x,A.y-c.y,B.x-c.x,B.y-c.y)>0;
}
void solve()
{
m=0;
for(int i=1;i<=n;i++)
{
if(i==now) continue;
b[++m]=a[i];b[m].id=i;
}
sort(b+1,b+1+m,cmp2);
for(int i=1;i<=m;i++)
{
st[b[i].id]=i;
}
for(int i=1;i<tp;i++)
{
if(abs(st[s[i]]-st[s[i+1]])==1||abs(st[s[i]]-st[s[i+1]])==m-1)
ans++;
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+n+1,cmp);
s[++tp]=1;
for(int i=2;i<=n;i++)
{
while(tp>=2&&calcompare(a[s[tp]].x-a[s[tp-1]].x,a[s[tp]].y-a[s[tp-1]].y,a[i].x-a[s[tp]].x,a[i].y-a[s[tp]].y)<=0)
{
tp--;
whe[s[tp+1]]=0;
}
s[++tp]=i;
whe[i]=1;
}
int sum1=tp;
for(int i=n-1;i>=1;i--)
{
if(!whe[i])
{
while(tp>sum1&&calcompare(a[s[tp]].x-a[s[tp-1]].x,a[s[tp]].y-a[s[tp-1]].y,a[i].x-a[s[tp]].x,a[i].y-a[s[tp]].y)<=0)
{
tp--;
whe[s[tp+1]]=0;
}
s[++tp]=i;
whe[i]=1;
}
}
for(int i=1;i<=tp;i++)
{
vis[s[i]]=1;
//cout<<s[i]<<"asdasd"<<endl;
}
for(int i=1;i<=n;i++)
{
if(!vis[i]) now=i,solve();
}
cout<<ans+1;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3936kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3824kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
6
result:
wrong answer 1st numbers differ - expected: '7', found: '6'