QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#235327#2838. 2D Geometryyiyiyi#WA 0ms4000kbC++141.6kb2023-11-02 17:16:052023-11-02 17:16:07

Judging History

你现在查看的是最新测评结果

  • [2023-11-02 17:16:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4000kb
  • [2023-11-02 17:16:05]
  • 提交

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'