제출 #956276

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
956276	2024-04-01 13:25:23	chrisvilches	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	2564 ms	3908 KiB

dragon2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
vector<int> mid_it;
struct Point {
  int x, y;
  int idx;
  Point operator-(const Point& p) const { return {x - p.x, y - p.y, idx}; }
  Point operator+(const Point& p) const { return {x + p.x, y + p.y, idx}; }
  long long cross(const Point& p) const {
    return x * (long long)p.y - y * (long long)p.x;
  }
  Point negate() const { return {-x, -y, idx}; }
};
short orientation(const Point& o, const Point& a, const Point& b) {
  const long long x = (a - o).cross(b - o);
  return (x > 0) - (x < 0);
}
Point A, B;
bool above(const Point& p) { return B.cross(p) > 0; }
Point to_upper(const Point& p) { return above(p) ? p : p.negate(); }
bool operator<(const Point& p, const Point& q) {
  return to_upper(p).cross(to_upper(q)) > 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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