QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#426553 | #7906. Almost Convex | yuanyq5523 | WA | 1ms | 3988kb | C++17 | 1.7kb | 2024-05-31 15:08:50 | 2024-05-31 15:08:51 |
Judging History
answer
#include <bits/stdc++.h>
#define endl "\n"
#define LL long long
using namespace std;
const int N=2e3+3;
const double eps=1e-12;
int n,top,ans,rk[N];
bool flag[N];
struct point{double x,y; int idx;}p[N],s[N],Pole;
vector<point>tubao;
point operator+(point& a,point& b){return point({a.x+b.x,a.y+b.y,0});}
point operator-(point& a,point& b){return point({a.x-b.x,a.y-b.y,0});}
double cross(point a,point b,point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
double cross(point a,point b){return a.x*b.y-b.x*a.y;}
bool cmp1(point a,point b){
return cross(a-Pole,b-Pole)>0;
}
bool cmp2(point a,point b){
if (a.x==b.x) return a.y<b.y;
else return a.x<b.x;
}
void Andrew(){
sort(p+1,p+n+1,cmp2);
for (int i=1;i<=n;i++){
while (top>1 && cross(s[top-1],s[top],p[i])<=0) top--;
s[++top]=p[i];
}
int t=top;
for (int i=n-1;i>=1;i--){
while (top>t && cross(s[top-1],s[top],p[i])<=0) top--;
s[++top]=p[i];
}
for (int i=1;i<=top;i++){
tubao.push_back(s[i]);
flag[s[i].idx]=true;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for (int i=1;i<=n;i++){
cin>>p[i].x>>p[i].y;
p[i].idx=i;
}
Andrew();
for (int i=1;i<=n;i++){
if (flag[p[i].idx]) continue;
Pole=p[i]; vector<point>tmp;
for (int j=1;j<=n;j++){
if (p[j].idx==Pole.idx) continue;
tmp.push_back(p[j]);
}
sort(tmp.begin(),tmp.end(),cmp1);
for (int j=0;j<n-1;j++){
rk[tmp[j].idx]=j;
}
for (int j=0;j<top-1;j++){
int idx1=tubao[j].idx;
int idx2=tubao[j+1].idx;
if ((rk[idx1]+1)%(n-1)==rk[idx2] || (rk[idx2]+1)%(n-1)==rk[idx1]) ans++;
}
//cout<<p[i].idx<<" "<<ans<<endl;
}
cout<<ans+1<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3856kb
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: 3988kb
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: 0ms
memory: 3856kb
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: 3700kb
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'