Submission #955900

#	Time	Username	Problem	Language	Result	Execution time	Memory
955900		chrisvilches	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	2140 ms	4180 KiB

dragon2

#include <bits/stdc++.h>
using namespace std;

struct point {
  long long x, y;

  point() : x(0), y(0) {}

  point(long long _x, long long _y) : x(_x), y(_y) {}

  point &operator+=(const point &rhs) {
    x += rhs.x;
    y += rhs.y;
    return *this;
  }

  point &operator-=(const point &rhs) {
    x -= rhs.x;
    y -= rhs.y;
    return *this;
  }
};

point make_point(long long x, long long y) { return point(x, y); }

point operator+(point lhs, const point &rhs) { return lhs += rhs; }

point operator-(point lhs, const point &rhs) { return lhs -= rhs; }

int operator^(const point &lhs, const point &rhs) {
  return lhs.x * rhs.y - lhs.y * rhs.x;
}

bool ccw(const point &a, const point &b, const point &c) {
  // return ((c - a) ^ (b - a)) < 0;
  return (c.x - a.x) * (b.y - a.y) < (c.y - a.y) * (b.x - a.x);
}

bool ccw(const point &b, const point &c) { return ccw(point(), b, c); }

bool cpt(const point &a, const point &b, const point &c) {
  if (ccw(b, c))
    return ccw(b, a) && ccw(a, c);
  else
    return ccw(a, b) && ccw(c, a);
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<vector<point>> cat(M);
  for (int i = 0; i < N; i++) {
    long long x, y;
    int c;
    cin >> x >> y >> c;
    cat[c - 1].emplace_back(x, y);
  }

  long long sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  point S(sx, sy), T(tx, ty);

  int Q;
  cin >> Q;
  while (Q--) {
    int c1, c2;
    cin >> c1 >> c2;
    c1--, c2--;
    long long ans = 0;
    for (const point &p : cat[c1])
      for (const point &q : cat[c2]) ans += int(cpt(q - p, S - p, T - p));
    cout << ans << '\n';
  }
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40