QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#107995#2838. 2D Geometryl1924365846WA 8ms3824kbC++172.8kb2023-05-23 13:25:382023-05-23 13:25:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-23 13:25:40]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3824kb
  • [2023-05-23 13:25:38]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define int ll
#define ms(a,b) memset((a),(b),sizeof(a))
#define mc(a,b) memcpy((a),(b),sizeof(a))
#define PI acos(-1)
#define ssin(x) sin(x*PI/180.00)
#define ccos(x) cos(x*PI/180.00)
#define ttan(X) tan(x*PI/180.00)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define IOS ios::sync_with_stdio(false)
#define si(x) scanf("%d",&x)
#define sii(x, y) scanf("%d %d",&x, &y)
#define siii(x, y, z) scanf("%d %d %d",&x, &y, &z)
#define siiii(x, y, z, w) scanf("%d %d %d %d",&x, &y, &z, &w)
#define sl(x) scanf("%lld",&x)
#define sll(x, y) scanf("%lld %lld",&x, &y)
#define slll(x, y, z) scanf("%lld %lld %lld",&x, &y, &z)
#define sllll(x, y, z, w) scanf("%lld %lld %lld %lld",&x, &y, &z, &w)
#define pr(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define sd(x) scanf("%lf",&x)
#define sdd(x, y) scanf("%lf %lf",&x, &y)
#define sddd(x, y, z) scanf("%lf %lf %lf",&x, &y, &z)
#define sdddd(x, y, z, w) scanf("%lf %lf %lf %lf",&x, &y, &z, &w)
#define fi first
#define se second
#define pb push_back
#define mk make_mair

using namespace std;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int mod = 1e9 + 7;

const int P = 131;

const int N = 2e5 + 10, M = 3e6 + 10;

const int inf = 0x3f3f3f3f;

const ll lnf = 9e18;

const double eps = 1e-6;

int n;
struct F {
	int x, y;
} f[N];
map<int, int> ma;
map<int, int> mb;
map<PII, int> mp;

int check (int a, int b) {
	int x = f[a].x, y = f[a].y, xx = f[b].x, yy = f[b].y;
	int cnt = 2;

	for (int i = 0; i < n; i ++) {
		if (i != a && i != b) {
			int xxx = f[i].x, yyy = f[i].y;

			if ( (xxx - xx) * (y - yy) == (yyy - yy) * (x - xx) ) {
				cnt++;
			}
		}
	}

	return cnt;
}

void solve() {
	srand ( (unsigned) time (NULL) );

	while (~scanf ("%lld", &n) ) {
		ma.clear(), mb.clear();
		mp.clear();
		int kk = 0;

		for (int i = 0; i < n; i ++) {
			int x, y;
			sll (x, y);
			f[i] = {x, y};
			ma[x]++;
			mb[y]++;
			kk = max (kk, max (ma[x], mb[y]) );
		}

		for (int i = 0; i < 5000; i ++) {
			int x = rand() % n, y = rand() % n;

			if (x == y || mp[ {x, y}] == 1)
				continue;
			mp[ {x, y}] = 1;

			kk = max (kk, check (x, y) );
		}

		if (kk <= (n - kk) * 2) {
			puts ("0");
		}
		else {
			printf ("%lld\n", kk - 2 * (n - kk) );
		}
	}
}

signed main() {
	//	IOS;
	//	cin.tie (0);
	//	cout.tie (0);
	int T (1);
	//	sl (T);

	while ( T-- ) {
		solve();
	}

	return 0;
}
/*
4
0 0
0 1
0 2
1 1
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2
*/

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

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: 8ms
memory: 3660kb

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
0
4
0
2
0
0
5
0
0
0
0
0
0
0
3
0
6

result:

wrong answer 6th lines differ - expected: '1', found: '0'