QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#234008 | #2838. 2D Geometry | SGColin# | WA | 0ms | 3920kb | C++17 | 1.3kb | 2023-11-01 12:47:57 | 2023-11-01 12:47:57 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
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 x[N], y[N];
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
rep(i, 1, n) x[i] = rd(), y[i] = rd();
if (n <= 2) {printf("%d\n", n); continue;}
auto calc = [&](int i, int j) {
ll dx = x[i] - x[j];
ll dy = y[i] - y[j];
ll z = dy * x[i] - dx * y[i];
int cnt = 0;
rep(p, 1, n) if (dy * x[p] - dx * y[p] == z) ++cnt;
return cnt - (n - cnt) * 2;
};
int ans = 0;
if (n <= 100) rep(i, 1, n) rep(j, i + 1, n) ans = max(ans, calc(i, j));
else rep(i, 1, 100) {
int u = rand() % n + 1, v = rand() % n + 1;
while(u == v) v = rand() % n + 1;
ans = max(ans, calc(u, v));
}
printf("%d\n", ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
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: 3920kb
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'