oj.uz

Submission #448418

# Submission time Handle Problem Language Result Execution time Memory
448418 2021-07-30T06:39:00 Z BERNARB01 Relay (COI16_relay) C++17
37 / 100
 1915 ms 4828 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;
	}
	bool byYs(const point& me, const point& other) {
		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++;
		}
		long long 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);
	long long n;
	cin >> n;
	vector<point> pts(n);
	for (long long i = 0; i < n; i++) {
		cin >> pts[i];
	}
	cin >> m;
	p.resize(m + 1);
	for (long long i = 0; i < m; i++) {
		cin >> p[i];
	}
	p[m] = p[0];
	long long md = 0;
	vector<point> tr, trr;
	for (long long i = 1; i < n; i++) {
		if (connect(pts[0], pts[i])) {
			md++;
			tr.emplace_back(pts[i]);
		} else {
			trr.emplace_back(pts[i]);
		}
	}
	long long re = 0;
	vector<long long> vis(n, 0);
	auto TRY = [&](const point& pt0) {
		for (long long i = 0; i < (long long) trr.size(); i++) {
			if (!vis[i] && connect(pt0, trr[i])) {
				vis[i] = 1;
				re++;
			}
		}
	};
	sort(tr.begin(), tr.end());
	for (long long itr = 0; itr < 2; itr++) {
		if (itr == 1) {
			sort(tr.begin(), tr.end(), byYs);
		}
		TRY(tr[0]);
		TRY(tr[tr.size() - 1]);
		for (long long i = 1; i + 1 < (long long) tr.size(); i++) {
			if (!itr && tr[i].x != tr[i + 1].x) {
				TRY(tr[i]);
				break;
			}
			if (itr && tr[i].y != tr[i + 1].y) {
				TRY(tr[i]);
				break;
			}
		}
		for (long long i = (long long) tr.size() - 2; i >= 1; i--) {
			if (!itr && tr[i].x != tr[i - 1].x) {
				TRY(tr[i]);
				break;
			}
			if (itr && tr[i].y != tr[i - 1].y) {
				TRY(tr[i]);
				break;
			}
		}
	}
	cout << md + re << '\n';
	return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 580 ms 448 KB Output is correct
12 Correct 571 ms 492 KB Output is correct
13 Correct 194 ms 444 KB Output is correct
14 Correct 155 ms 396 KB Output is correct
15 Correct 290 ms 472 KB Output is correct
16 Correct 228 ms 468 KB Output is correct
17 Correct 225 ms 452 KB Output is correct
18 Correct 130 ms 468 KB Output is correct
19 Correct 293 ms 472 KB Output is correct
20 Correct 229 ms 472 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 1915 ms 4288 KB Output is correct
12 Correct 1862 ms 4160 KB Output is correct
13 Correct 825 ms 4320 KB Output is correct
14 Correct 950 ms 4456 KB Output is correct
15 Correct 1091 ms 4648 KB Output is correct
16 Correct 1080 ms 4364 KB Output is correct
17 Correct 530 ms 4784 KB Output is correct
18 Correct 494 ms 4828 KB Output is correct
19 Incorrect 662 ms 4388 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 332 KB Output is correct
2 Correct 6 ms 332 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 204 KB Output is correct
9 Correct 3 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 580 ms 448 KB Output is correct
12 Correct 571 ms 492 KB Output is correct
13 Correct 194 ms 444 KB Output is correct
14 Correct 155 ms 396 KB Output is correct
15 Correct 290 ms 472 KB Output is correct
16 Correct 228 ms 468 KB Output is correct
17 Correct 225 ms 452 KB Output is correct
18 Correct 130 ms 468 KB Output is correct
19 Correct 293 ms 472 KB Output is correct
20 Correct 229 ms 472 KB Output is correct
21 Correct 1915 ms 4288 KB Output is correct
22 Correct 1862 ms 4160 KB Output is correct
23 Correct 825 ms 4320 KB Output is correct
24 Correct 950 ms 4456 KB Output is correct
25 Correct 1091 ms 4648 KB Output is correct
26 Correct 1080 ms 4364 KB Output is correct
27 Correct 530 ms 4784 KB Output is correct
28 Correct 494 ms 4828 KB Output is correct
29 Incorrect 662 ms 4388 KB Output isn't correct
30 Halted 0 ms 0 KB -