QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556134 | #2838. 2D Geometry | ucup-team1198# | TL | 0ms | 3616kb | C++20 | 1.4kb | 2024-09-10 15:17:32 | 2024-09-10 15:17:34 |
Judging History
answer
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
struct Point{
long long x;
long long y;
Point(long long x, long long y): x(x), y(y) {}
Point(): x(0), y(0) {}
};
Point operator-(const Point& A, const Point& B) {
return Point(A.x - B.x, A.y - B.y);
}
long long cross(const Point& A, const Point& B) {
return A.x * B.y - A.y * B.x;
}
bool same_line(const Point& A, const Point& B, const Point& C) {
return cross(C - A, C - B) == 0;
}
mt19937_64 rnd(179);
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
while (cin >> n) {
vector<Point> A(n);
for (int i = 0; i < n; ++i)
cin >> A[i].x >> A[i].y;
int max_line = 1;
for (int _ = 0; _ < 60; ++_) {
int x = rnd() % n;
int y = x;
while (y == x)
y = rnd() % n;
int cnt = 0;
for (auto P : A)
cnt += same_line(A[x], A[y], P);
max_line = max(max_line, cnt);
}
if (max_line >= 2 * (n - max_line)) {
cout << n - 3 * (n - max_line) << '\n';
} else {
cout << n % 3 << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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 ...