QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#235327 | #2838. 2D Geometry | yiyiyi# | WA | 0ms | 4000kb | C++14 | 1.6kb | 2023-11-02 17:16:05 | 2023-11-02 17:16:07 |
Judging History
answer
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<bitset>
#include<set>
#define ll long long
#define lowbit(x) x&(-x)
#define mp make_pair
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define per(i,n,x) for(int i=n;i>=x;i--)
#define forE(i,x) for(int i=head[x];i;i=nxt[i])
#define pii pair<ll,int>
#define fi first
#define se second
using namespace std;
const int maxn=5e5+5;
const int mod=998244353;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+(c-'0');
c=getchar();
}
return x*f;
}
int n;
pii p[maxn];
int cross(pii x,pii y)
{
return x.first*y.second-x.second*y.first;
}
signed main()
{
srand(time(0));
while(scanf("%lld",&n) != EOF)
{
rep(i,1,n) {p[i]={read(),read()};}
if(n==1||n==2) {printf("%lld\n",n);continue;}
int T=100,ans=n;
while(T--)
{
int cnt=2;
int x=rand()%n+1,y=rand()%n+1;
while(x==y) x=rand()%n+1,y=rand()%n+1;
pii v = {p[x].first-p[y].first,p[x].second-p[y].second};
rep(i,1,n)
{
if(i==x||i==y) continue;
pii u = {p[i].first-p[y].first,p[i].second-p[y].second};
if(cross(u,v) == 0) cnt++;
}
ans=min(ans,max(0,cnt-(2*(n-cnt))));
}
printf("%lld\n",ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4000kb
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
Wrong Answer
time: 0ms
memory: 3908kb
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 0 0 4 0 0 0 0 5 0 0 0 0 0 0 0 0 0 6
result:
wrong answer 5th lines differ - expected: '1', found: '0'