oj.uz

Submission #448417

# Submission time Handle Problem Language Result Execution time Memory
448417 2021-07-30T06:37:31 Z BERNARB01 Relay (COI16_relay) C++17
37 / 100
 1969 ms 4748 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++;
		}
		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<point> tr, trr;
	for (int i = 1; i < n; i++) {
		if (connect(pts[0], pts[i])) {
			md++;
			tr.emplace_back(pts[i]);
		} else {
			trr.emplace_back(pts[i]);
		}
	}
	int re = 0;
	vector<int> vis(n, 0);
	auto TRY = [&](const point& pt0) {
		for (int i = 0; i < (int) trr.size(); i++) {
			if (!vis[i] && connect(pt0, trr[i])) {
				vis[i] = 1;
				re++;
			}
		}
	};
	sort(tr.begin(), tr.end());
	for (int itr = 0; itr < 2; itr++) {
		if (itr == 1) {
			sort(tr.begin(), tr.end(), byYs);
		}
		TRY(tr[0]);
		TRY(tr[tr.size() - 1]);
		for (int i = 1; i + 1 < (int) 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 (int i = (int) 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 4 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 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 4 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 591 ms 544 KB Output is correct
12 Correct 558 ms 496 KB Output is correct
13 Correct 194 ms 416 KB Output is correct
14 Correct 186 ms 452 KB Output is correct
15 Correct 285 ms 476 KB Output is correct
16 Correct 233 ms 468 KB Output is correct
17 Correct 238 ms 432 KB Output is correct
18 Correct 131 ms 508 KB Output is correct
19 Correct 297 ms 412 KB Output is correct
20 Correct 242 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 4 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 1969 ms 4316 KB Output is correct
12 Correct 1897 ms 4168 KB Output is correct
13 Correct 853 ms 4152 KB Output is correct
14 Correct 966 ms 4240 KB Output is correct
15 Correct 1100 ms 4348 KB Output is correct
16 Correct 1135 ms 4060 KB Output is correct
17 Correct 551 ms 4668 KB Output is correct
18 Correct 500 ms 4748 KB Output is correct
19 Incorrect 656 ms 4048 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 4 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 591 ms 544 KB Output is correct
12 Correct 558 ms 496 KB Output is correct
13 Correct 194 ms 416 KB Output is correct
14 Correct 186 ms 452 KB Output is correct
15 Correct 285 ms 476 KB Output is correct
16 Correct 233 ms 468 KB Output is correct
17 Correct 238 ms 432 KB Output is correct
18 Correct 131 ms 508 KB Output is correct
19 Correct 297 ms 412 KB Output is correct
20 Correct 242 ms 472 KB Output is correct
21 Correct 1969 ms 4316 KB Output is correct
22 Correct 1897 ms 4168 KB Output is correct
23 Correct 853 ms 4152 KB Output is correct
24 Correct 966 ms 4240 KB Output is correct
25 Correct 1100 ms 4348 KB Output is correct
26 Correct 1135 ms 4060 KB Output is correct
27 Correct 551 ms 4668 KB Output is correct
28 Correct 500 ms 4748 KB Output is correct
29 Incorrect 656 ms 4048 KB Output isn't correct
30 Halted 0 ms 0 KB -