| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 448407 |
2021-07-30T05:38:53 Z |
BERNARB01 |
Relay (COI16_relay) |
C++17 |
|
2000 ms |
4872 KB |
#include <bits/stdc++.h>
using namespace std;
namespace geo {
using T = long long;
class point {
public:
T x, y;
point() {
x = y = 0;
}
point(T _x, T _y) {
x = _x; y = _y;
}
friend istream& operator>>(istream&, point&);
friend ostream& operator<<(ostream&, const point&);
bool operator<(const point& other) const {
if (x == other.x) {
return y < other.y;
}
return x < other.x;
}
bool operator ==(const point& other) const {
return (x == other.x && y == other.y);
}
point operator +(const point& other) const {
return point(x + other.x, y + other.y);
}
point operator -(const point& other) const {
return point(x - other.x, y - other.y);
}
point operator *(const T& _k) const {
return point(x * _k, y * _k);
}
void operator -=(const point& other) {
x -= other.x; y -= other.y;
}
void operator +=(const point& other) {
x += other.x; y += other.y;
}
void norm() {
long long g = gcd(x, y);
x /= g; y /= g;
}
T operator *(const point& other) const {
return x * other.y - other.x * y;
}
T tri(const point& _p1, const point& _p2) const {
return (_p1 - *this) * (_p2 - *this);
}
T m_dist() const {
return std::abs(x + y);
}
T m_dist(const point& other) const {
return std::abs(x - other.x) + std::abs(y - other.y);
}
long double abs() const {
return sqrtl(x * x + y * y);
}
long double dist(const point& other) const {
return (other - *this).abs();
}
}; // point
istream& operator >>(istream& in, point& _p) {
in >> _p.x >> _p.y;
return in;
}
ostream& operator <<(ostream& out, const point& _p) {
out << "(" << _p.x << ", " << _p.y << ")";
return out;
}
struct byYs {
bool operator ()(const point& me, const point& other) const {
if (me.y == other.y) {
return me.x < other.x;
}
return me.y < other.y;
}
};
class segment {
public:
point p1, p2;
segment() {}
segment(point _p1, point _p2) {
p1 = _p1; p2 = _p2;
if (p1.x > p2.x) {
swap(p1, p2);
}
}
int side(const point& _p) const {
T _ret = p1.tri(_p, p2);
return (_ret > 0) - (_ret < 0);
}
T len() const {
return p2.dist(p1);
}
long double dist(const point& _p) const {
return _p.tri(p1, p2) / this->len();
}
T latt() {
return __gcd(abs(p1.x - p2.x), abs(p1.y - p2.y));
}
bool onMe(const point& _p) const {
return (_p.tri(p1, p2) == 0
&& min(p1.x, p2.x) <= _p.x && _p.x <= max(p1.x, p2.x)
&& min(p1.y, p2.y) <= _p.y && _p.y <= max(p1.y, p2.y));
}
int intrsct(const segment& _s) const {
if ((p2 - p1) * (_s.p2 - _s.p1) == 0) {
return -1;
}
if (side(_s.p1) * side(_s.p2) > 0 || _s.side(p1) * _s.side(p2) > 0) {
return 0;
}
return 1;
}
}; // segment
class polygon {
public:
int n;
vector<point> p;
polygon() {
n = 0;
}
polygon(const vector<point>& _p) {
p = _p;
n = p.size();
}
T area2() const {
T S = 0;
for (int i = 0; i < n; i++) {
S += p[i] * p[i + 1 == n ? 0 : i + 1];
}
return abs(S);
}
int inside(const point& _p) const {
int cnt = 0;
bool boundary = 0;
for (int i = 0; i < n; i++) {
segment _s(p[i], p[i + 1 == n ? 0 : i + 1]);
if (_s.onMe(_p)) {
boundary = true;
break;
}
cnt += (_s.p1.x <= _p.x && _p.x < _s.p2.x && _p.tri(_s.p1, _s.p2) < 0);
}
if (boundary == true) {
return 0;
}
return (cnt & 1 ? 1 : -1);
}
pair<long long, long long> latt() const {
long long A = 0, B = 0, S = area2();
for (int i = 0; i < n; i++) {
B += segment(p[i], p[i + 1 == n ? 0 : i + 1]).latt();
}
A = (S - B + 2) / 2;
return pair<long long, long long>(A, B);
}
vector<point> convex_hull() const {
vector<point> pp = p, s, ret;
sort(pp.begin(), pp.end());
s.emplace_back(pp[0]);
for (int i = 1; i < n; i++) {
while (s.size() > 1 && s[s.size() - 2].tri(pp[i], s.back()) < 0) {
s.pop_back();
}
s.emplace_back(pp[i]);
}
ret = s;
s.clear();
s.emplace_back(pp[0]);
for (int i = 1; i < n; i++) {
while (s.size() > 1 && s[s.size() - 2].tri(pp[i], s.back()) > 0) {
s.pop_back();
}
s.emplace_back(pp[i]);
}
for (int i = 1; i < (int) s.size() - 1; i++) {
ret.emplace_back(s[i]);
}
return ret;
}
}; // polygon
point O(0, 0);
} // namespace geo
using namespace geo;
int m;
vector<point> p;
bool connect(const point& p1, const point& p2) {
segment s(p1, p2);
int itsc = 0, vtch = 0;
for (int i = 0; i < m; i++) {
if (s.onMe(p[i])) {
vtch++;
}
if (s.onMe(p[i + 1])) {
vtch++;
}
int cs = s.intrsct(segment(p[i], p[i + 1]));
if (cs == -1 && (s.onMe(p[i]) || s.onMe(p[i + 1]))) {
return true;
}
if (s.onMe(p[i]) || s.onMe(p[i + 1])) {
continue;
}
if (cs == 1) {
itsc++;
}
}
return !(itsc > 1 || vtch > 3 || (itsc > 0 && vtch > 1));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<point> pts(n);
for (int i = 0; i < n; i++) {
cin >> pts[i];
}
cin >> m;
p.resize(m + 1);
for (int i = 0; i < m; i++) {
cin >> p[i];
}
p[m] = p[0];
int md = 0;
vector<int> tr, trr;
for (int i = 1; i < n; i++) {
if (connect(pts[0], pts[i])) {
md++;
tr.emplace_back(i);
} else {
trr.emplace_back(i);
}
}
int re = 0;
vector<int> vis(n, 0);
for (const auto& pti : tr) {
for (int i = 0; i < (int) trr.size(); i++) {
if (!vis[i] && connect(pts[pti], pts[trr[i]])) {
vis[i] = 1;
re++;
}
}
}
cout << md + re << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
332 KB |
Output is correct |
| 2 |
Correct |
34 ms |
332 KB |
Output is correct |
| 3 |
Correct |
17 ms |
336 KB |
Output is correct |
| 4 |
Correct |
30 ms |
332 KB |
Output is correct |
| 5 |
Correct |
17 ms |
332 KB |
Output is correct |
| 6 |
Correct |
28 ms |
336 KB |
Output is correct |
| 7 |
Correct |
16 ms |
336 KB |
Output is correct |
| 8 |
Correct |
15 ms |
332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
324 KB |
Output is correct |
| 10 |
Correct |
7 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
332 KB |
Output is correct |
| 2 |
Correct |
34 ms |
332 KB |
Output is correct |
| 3 |
Correct |
17 ms |
336 KB |
Output is correct |
| 4 |
Correct |
30 ms |
332 KB |
Output is correct |
| 5 |
Correct |
17 ms |
332 KB |
Output is correct |
| 6 |
Correct |
28 ms |
336 KB |
Output is correct |
| 7 |
Correct |
16 ms |
336 KB |
Output is correct |
| 8 |
Correct |
15 ms |
332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
324 KB |
Output is correct |
| 10 |
Correct |
7 ms |
332 KB |
Output is correct |
| 11 |
Execution timed out |
2072 ms |
528 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
332 KB |
Output is correct |
| 2 |
Correct |
34 ms |
332 KB |
Output is correct |
| 3 |
Correct |
17 ms |
336 KB |
Output is correct |
| 4 |
Correct |
30 ms |
332 KB |
Output is correct |
| 5 |
Correct |
17 ms |
332 KB |
Output is correct |
| 6 |
Correct |
28 ms |
336 KB |
Output is correct |
| 7 |
Correct |
16 ms |
336 KB |
Output is correct |
| 8 |
Correct |
15 ms |
332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
324 KB |
Output is correct |
| 10 |
Correct |
7 ms |
332 KB |
Output is correct |
| 11 |
Execution timed out |
2067 ms |
4872 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
332 KB |
Output is correct |
| 2 |
Correct |
34 ms |
332 KB |
Output is correct |
| 3 |
Correct |
17 ms |
336 KB |
Output is correct |
| 4 |
Correct |
30 ms |
332 KB |
Output is correct |
| 5 |
Correct |
17 ms |
332 KB |
Output is correct |
| 6 |
Correct |
28 ms |
336 KB |
Output is correct |
| 7 |
Correct |
16 ms |
336 KB |
Output is correct |
| 8 |
Correct |
15 ms |
332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
324 KB |
Output is correct |
| 10 |
Correct |
7 ms |
332 KB |
Output is correct |
| 11 |
Execution timed out |
2072 ms |
528 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
