QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#62128 | #2838. 2D Geometry | RWLinno# | TL | 3ms | 3532kb | C++14 | 797b | 2022-11-17 15:06:20 | 2022-11-17 15:06:22 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+7;
struct Point{
int x,y;
}p[N];
int n;
signed main(){
srand(time(0));
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;++i){
scanf("%d%d",&p[i].x,&p[i].y);
}
int mx=2,ans=n; //最大链长度
for(int t=1;t<=500;++t){
int A=rand()%n+1,B=rand()%n+1;
while(A==B) A=rand()%n+1,B=rand()%n+1;
int sum=2;
for(int C=1;C<=n;++C){
if(A==C||B==C) continue;
if((p[C].y-p[B].y)*(p[B].x-p[A].x)==(p[C].x-p[B].x)*(p[B].y-p[A].y)){
++sum;
}
if(2*n>3*sum) ans=min(ans,n%3);
mx=max(mx,sum);
}
}
ans=min(ans,mx-2*(n-mx));
printf("%d\n",ans);
}
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3532kb
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: -100
Time Limit Exceeded
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 ...