QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#935101#2297. Flatland OlympicsAngelOlanWA 1ms3584kbC++232.1kb2025-03-15 12:45:212025-03-15 12:45:22

Judging History

This is the latest submission verdict.

  • [2025-03-15 12:45:22]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3584kb
  • [2025-03-15 12:45:21]
  • Submitted

answer

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// Pura Gente del Coach Moy y de la Alexbriza

using ll = long long;
using T = ll;

struct Point {
  int x, y;

  Point() {}
  Point(int x, int y) : x(x), y(y) {}

  void read() {
    cin >> x >> y;
  }

  void print() {
    cout << x << ' ' << y << '\n';
  }

  T sq() { return (T)x * x + (T)y * y; }

  T dot(Point p) { return (T)x * p.x + (T)y * p.y; }
  T cross(Point p) const { return (T)x * p.y - (T)y * p.x; }

  Point operator-(Point p) const { return Point(x - p.x, y - p.y); }
};

T orient(Point a, Point b) { return a.cross(b); }

int half(Point p, Point v) { return v.cross(p) < 0 || (v.cross(p) == 0 && v.dot(p) < 0); }

inline void polarSortAround(Point o, Point dir, vector<Point>& P, bool inv = false) {
  sort(P.begin(), P.end(), [&](Point p, Point q) -> bool {
    auto ta = make_tuple(half(p - o, dir), 0);
    auto tb = make_tuple(half(q - o, dir), (p - o).cross(q - o));
    if (ta != tb) {
      return ta < tb;
    }
    return ((p - o).sq() < (q - o).sq()) ^ inv;
  });
  if (inv) {
    reverse(P.begin(), P.end());
  }
}

template <class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

ll f(Point a, Point b, vector<Point>& P, bool inv = false) {
  Point dir = b - a;
  polarSortAround(a, dir, P, inv);

  oset<ll> oset;
  ll ret = 0;
  for (Point p : P) {
    T dot = dir.dot(p - a);
    int ord = int(oset.order_of_key(dot + inv));
    ret += ord;
    oset.insert(dot);
  }
  return ret;
}

ll gauss(int n) {
  return (ll)n * (n + 1) >> 1;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  Point s, e;
  s.read(), e.read();
  
  int n;
  cin >> n;

  vector<Point> P(n);
  for (Point& p : P) {
    p.read();
    p = p - s;
  }

  e = (e - s);
  s = (s - s);

  vector<int> inLine(2);
  vector<Point> L, R;
  for (Point& p : P) {
    T ori = orient(e, p);
    if (ori > 0) {
      L.push_back(p);
    } else if (ori < 0) {
      R.push_back(p);
    } else {
      ++inLine[e.dot(p) < 0];
    }
  }

  ll ans = f(s, e, L) + f(s, e, R, true) + f(e, s, L, true) + f(e, s, R);
  cout << ans << '\n';
}

详细

Test #1:

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

input:

0 0 1 0
2
-1 0
2 0

output:

0

result:

ok single line: '0'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3584kb

input:

0 0 1 0
4
-1 0
-2 0
2 0
3 0

output:

0

result:

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