QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#59702 | #2838. 2D Geometry | XrkArul# | WA | 1ms | 3576kb | C++17 | 1.7kb | 2022-10-31 20:54:29 | 2022-10-31 20:54:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using point_t = long long;
constexpr point_t eps = 1e-8;
template<typename T> struct point {
T x, y;
point<T> operator-(point a) { return {x - a.x, y - a.y}; }
T operator^(point a) { return x * a.y - y * a.x; }
int toleft(point a) { auto t = (*this) ^ a; return (t > eps) - (t < -eps); }
};
using Point = point<point_t>;
#define int long long
signed main() {
int n; while (cin >> n) {
vector<Point> p(n);
for (auto &[x, y] : p) scanf("%lld %lld", &x, &y);
auto cnt_in_line = [&](int i, int j) {
Point i_j = p[i] - p[j];
int res = 0;
for (int k = 0; k < n; k++) {
if (i_j.toleft(p[k] - p[j]) == 0) res++;
}
return res;
};
if (n <= 100) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cnt = cnt_in_line(i, j);
if (cnt * 3 >= 2 * n) {
cout << n - (n - cnt) * 3 << endl;
goto END;
}
}
if (i == n - 1) cout << 0 << endl;
}
} else {
for (int _ = 0; _ < 200; _++) {
int i = rand() % n, j = i;
while (j == i) j = rand() % n;
int cnt = cnt_in_line(i, j);
if (cnt * 3 > n || cnt * 2 >= n) {
if (cnt * 3 >= 2 * n) cout << n - (n - cnt) * 2 << endl;
else cout << 0 << endl;
goto END;
}
if (_ == 14) cout << 0 << endl;
}
}
END: ;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
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: 3572kb
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'