QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#21766 | #2838. 2D Geometry | WhybullYMe# | WA | 4ms | 6924kb | C++14 | 1.4kb | 2022-03-08 15:02:11 | 2022-05-08 04:02:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5+10;
mt19937 rndNum(chrono::system_clock::now().time_since_epoch().count());
template<class T>
inline T genRnd(const T &limL,const T &limR){
uniform_int_distribution<T>limLR(limL,limR);
return limLR(rndNum);
}
inline ll sqr(ll k){return k*k;}
struct vec{
ll x,y;
inline vec(ll x_=0,ll y_=0):x(x_),y(y_){}
inline vec operator-(const vec &k){
return vec(x-k.x,y-k.y);
}
inline bool operator<(const vec &k)const{
return x!=k.x?x<k.x:y<k.y;
}
inline ll cross(const vec &k){
return x*k.y-y*k.x;
}
inline ll norm(){
return x*x+y*y;
}
inline ll dist(const vec &k){
return sqrt(sqr(x-k.x)+sqr(y-k.y));
}
}a[maxn],st[maxn];
inline bool cmp(const int &x,const int &y){
ll det=(a[x]-a[0]).cross(a[y]-a[0]);
return det?det>0:(a[x]-a[0]).norm()<(a[y]-a[0]).norm();
}
int n,id[maxn],tp;
inline int graham(){
iota(id+1,id+n+1,1);
int ret=0;
for(int T=1;T<=50;++T){
a[0]={genRnd(0,(int)1e9),genRnd(0,(int)1e9)};
ri cnt=0;
sort(id+1,id+n+1,cmp);
st[tp=1]=a[id[1]];
for(ri i=2;i<=n;++i){
ri j=id[i];
if(tp>1&&(a[j]-st[tp-1]).cross(st[tp]-st[tp-1]))cnt+=3,tp-=2;
else st[++tp]=a[j];
}
ret=max(ret,cnt);
}
return ret;
}
int main(){
srand(time(0));
while(~scanf("%d",&n)){
for(ri i=1;i<=n;++i)scanf("%lld%lld",&a[i].x,&a[i].y);
printf("%d\n",n-graham());
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 6924kb
input:
3 0 0 0 1 0 2 3 0 0 0 1 1 0 6 0 0 0 1 0 2 0 3 1 1 1 2
output:
3 0 0
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 6856kb
input:
1 0 0 2 0 0 1 1 3 0 0 0 1 0 2 3 0 0 0 1 1 0 4 3 0 0 2 3 3 3 1 4 2 3 1 1 0 3 0 2 4 0 0 0 3 0 2 0 1 5 8 6 9 2 2 3 7 4 1 5 5 2 2 4 2 6 2 7 2 0 4 5 3 7 5 4 4 4 9 4 9 9 5 5 4 5 9 5 5 4 3 1 0 5 3 2 1 2 7 2 6 2 5 2 6 7 2 7 9 0 3 8 8 4 4 3 8 6 2 8 2 5 3 5 3 8 2 0 0 2 6 2 3 8 4 2 9 2 2 2 6 4 9 6 2 1 7 6 6 5 ...
output:
1 2 3 0 1 1 4 2 2 2 2 5 0 0 0 0 0 0 0 3 0 6
result:
ok 22 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 6924kb
input:
7 0 1 0 0 7 7 6 2 6 9 4 4 3 5 7 3 7 3 2 9 1 0 6 1 8 5 0 9 5 7 3 7 2 3 4 5 6 7 7 7 5 8 4 7 7 1 6 5 7 7 2 3 5 0 8 8 8 3 8 7 1 8 3 4 8 8 1 9 7 8 1 7 0 0 7 6 9 2 7 4 5 2 1 4 6 2 3 7 6 7 3 1 1 9 5 7 6 6 5 2 5 1 5 3 7 6 4 1 6 7 3 5 4 2 3 0 0 3 2 7 2 9 4 9 8 9 8 0 1 7 2 6 6 2 7 3 5 4 0 4 1 4 3 0 8 4 7 4 6 ...
output:
1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1
result:
ok 21 lines
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 6916kb
input:
8 3 2 4 4 3 9 7 9 9 3 9 1 4 2 5 3 8 0 6 0 2 1 6 9 9 5 5 8 4 6 8 0 9 8 1 8 8 1 9 0 1 3 6 4 3 6 4 0 1 6 8 5 3 1 0 0 1 7 1 3 7 8 8 6 4 6 2 8 3 3 7 8 0 8 6 3 0 4 2 3 5 3 5 4 8 6 2 9 7 3 2 6 5 2 2 1 5 4 7 2 5 8 1 1 1 0 1 5 2 8 8 9 8 8 0 0 1 4 8 8 0 3 3 8 2 5 5 3 0 0 0 6 2 8 9 8 3 9 3 5 3 1 6 5 6 2 1 1 8 ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
result:
wrong answer 25th lines differ - expected: '2', found: '5'