QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#734565 | #7906. Almost Convex | xinlengweishang | WA | 0ms | 3920kb | C++20 | 2.4kb | 2024-11-11 12:42:39 | 2024-11-11 12:42:40 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define maxn 10010
using namespace std;
ll n;
struct node{
ll x;
ll y;
}s[maxn],que[maxn],up[maxn],down[maxn];
ll check(node a,node b,node c){
ll dx1=a.x-c.x,dy1=a.y-c.y;
ll dx2=b.x-c.x,dy2=c.y-c.y;
return dx1*dy2-dx2*dy1;
}
bool cmp(node a,node b){
ll n=check(a,b,s[1]);
if(n>0) return 1;
else if(n==0)
return (a.x-s[1].x)*(a.x-s[1].x)<(b.x-s[1].x)*(b.x-s[1].x);
return 0;
}
//bool cmpup(node a,node b){
// ll n=check(a,b,s[1]);
// if(n>0) return 1;
// else if(n==0)
// return (a.x-s[1].x)*(a.x-s[1].x)<(b.x-s[1].x)*(b.x-s[1].x)
// else return 0;
//}
//bool cmpdown(node a,node b){
// ll n=check(a,b,s[1]);
// if(n>0) return 1;
// else if(n==0)
// return (a.x-s[1].x)*(a.x-s[1].x)<(b.x-s[1].x)*(b.x-s[1].x)
// else return 0;
//}
map<ll,map<ll,ll> > mp;
int check2(node a,node b){
if(mp[a.x][a.y]==1&&mp[b.x][b.y]==1) return 1;
return 0;
}
ll sslove(int x){
ll ans=0;
ll mid;
mid=s[x].x;
s[x].x=s[1].x;
s[1].x=mid;
mid=s[x].y;
s[x].y=s[1].y;
s[1].y=mid;
ll j=1,q=1;
for(int i=2;i<=n;i++){
if(s[i].y>s[1].y){
up[j]=s[i];
j++;
}
else if(s[i].y==s[1].y){
if(s[i].x>s[1].x){
up[j]=s[i];
j++;
}
else {
down[q]=s[i];
q++;
}
}
else {
down[q]=s[i];
q++;
}
}
sort(up+1,up+j,cmp);
sort(down+1,down+q,cmp);
for(int i=1;i<j-1;i++){
if(check2(up[i],up[i+1])) ans++;
}
for(int i=1;i<q-1;i++){
if(check2(down[i],down[i+1])) ans++;
}
if(check2(up[j-1],down[0])) ans++;
if(check2(up[0],down[q-1])) ans++;
return ans;
}
void slove(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&s[i].x,&s[i].y);
if(s[i].y<s[1].y||((s[i].y==s[1].y)&&(s[i].x<s[1].y))){
ll mid;
mid=s[i].y;
s[i].y=s[1].y;
s[1].y=mid;
mid=s[i].x;
s[i].x=s[1].x;
s[1].x=mid;
}//保证左下角的点位于s[1]
}
sort(s+2,s+n+1,cmp);
ll cnt=2;
que[1]=s[1];
for(int i=2;i<=n;i++){
while(cnt>2){
if(check(s[i],que[cnt-1],que[cnt-2])){
cnt--;
}
else break;
}
que[cnt]=s[i];
cnt++;
}
for(int i=1;i<cnt;i++){
mp[que[i].x][que[i].y]=1;
}
ll ans=0;
for(int i=1;i<=n;i++){
if(mp[s[i].x][s[i].y]) continue;
ans+=sslove(i);
}
printf("%lld",ans);
return ;
}
int main(){
int T=1;
while(T--) slove();
return 0;
}
/*
7
1 4
4 0
2 3
3 1
3 5
0 0
2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3920kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
11
result:
wrong answer 1st numbers differ - expected: '9', found: '11'