QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#233981#2838. 2D GeometrySGColin#WA 0ms3708kbC++171.7kb2023-11-01 11:53:382023-11-01 11:53:38

Judging History

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

  • [2023-11-01 11:53:38]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3708kb
  • [2023-11-01 11:53:38]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<ll, ll, ll> tlll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '0');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)

#define N 200007

ll n, x[N], y[N];

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

map<tlll, int> f;

int main() {
	while (scanf("%lld", &n) != EOF) {
		f.clear();
		rep(i, 1, n) x[i] = rd(), y[i] = rd();
		auto calc = [&](int i, int j) {
			ll dx = x[i] - x[j];
			ll dy = y[i] - y[j];
			ll g = gcd(abs(dx), abs(dy));
			dx /= g; dy /= g;
			if (dx < 0) dx = -dx, dy = -dy;
			else if (dx == 0) dy = abs(dy);
			++f[mt(dy, -dx, dy * x[i] - dx * y[i])];
		};
		if (n <= 100) {
			rep(i, 1, n) rep(j, i + 1, n) calc(i, j);
		} else {
			int tim = n * 100;
			rep(tt, 1, tim) {
				int i = rand() % (n - 1) + 1;
				int j = i + rand() % (n - i) + 1;
				calc(i, j);
			}
		}
		vector<pair<int, tlll> > s;
		for (auto [w, cnt] : f) s.eb(cnt, w);
		sort(all(s)); reverse(all(s));
		bool fl = false;
		per(i, min(10, (int)s.size() - 1), 0) {
			auto [a, b, c] = s[i].second;
			int cnt = 0;
			rep(i, 1, n) if (a * x[i] + b * y[i] == c) ++cnt;
			int rem = n - cnt;
			if (rem * 2 < cnt) {
				//printf("%lld %lld %lld\n", a, b, c);
				fl = true; printf("%d\n", cnt - rem * 2);	
			}
		}
		if (!fl) puts("0");
	}
	return 0;	
}

详细

Test #1:

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

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: 3636kb

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:

0
2
3
0
1
0
4
0
2
0
0
5
0
0
0
0
0
0
0
3
0
6

result:

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