QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21700#2838. 2D GeometryDaBenZhongXiaSongKuaiDi#TL 3ms3584kbC++201015b2022-03-08 14:19:542022-05-08 03:57:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 03:57:46]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:3584kb
  • [2022-03-08 14:19:54]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define int long long
#define mod 998244353
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
int tx[200005],ty[200005];
signed main()
{
	int n,x,y,sl;
	bool flag;
	srand(114514);
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
		{
			tx[i]=read();
			ty[i]=read();
		}
		flag=false;
		for(int i=1;i<=70;i++)
		{
			x=1LL*rand()*rand()%n+1;
			y=1LL*rand()*rand()%n+1;
			while(y==x)y=1LL*rand()*rand()%n+1;
			sl=0;
			for(int j=1;j<=n;j++)
			{
				if((tx[x]-tx[y])*(ty[j]-ty[x])-(ty[x]-ty[y])*(tx[j]-tx[x])==0)
				{
					sl++;
				}
			}
			if(sl>2*(n-sl))
			{
				//printf("%lld %lld\n",x,y);
				printf("%lld\n",sl*3-2*n);
				flag=true;
				break;
			}
		}
		if(flag==false)printf("%lld\n",n%3);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3584kb

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
...

output:


result: