QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556134#2838. 2D Geometryucup-team1198#TL 0ms3616kbC++201.4kb2024-09-10 15:17:322024-09-10 15:17:34

Judging History

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

  • [2024-09-10 15:17:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3616kb
  • [2024-09-10 15:17:32]
  • 提交

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;
}

詳細信息

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
...

output:


result: