oj.uz

Submission #448416

# Submission time Handle Problem Language Result Execution time Memory
448416 2021-07-30T06:34:51 Z BERNARB01 Relay (COI16_relay) C++17
37 / 100
 1944 ms 6852 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 (tr[i].x != tr[i + 1].x) {
				TRY(tr[i]);
				break;
			}
		}
		for (int i = (int) tr.size() - 2; i >= 1; i--) {
			if (tr[i].x != tr[i - 1].x) {
				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 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 356 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 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 356 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 581 ms 648 KB Output is correct
12 Correct 556 ms 624 KB Output is correct
13 Correct 195 ms 664 KB Output is correct
14 Correct 160 ms 548 KB Output is correct
15 Correct 289 ms 460 KB Output is correct
16 Correct 236 ms 560 KB Output is correct
17 Correct 234 ms 460 KB Output is correct
18 Correct 129 ms 520 KB Output is correct
19 Correct 298 ms 572 KB Output is correct
20 Correct 233 ms 524 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 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 356 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 1944 ms 4324 KB Output is correct
12 Correct 1918 ms 6200 KB Output is correct
13 Correct 868 ms 6204 KB Output is correct
14 Correct 987 ms 6184 KB Output is correct
15 Correct 1096 ms 6244 KB Output is correct
16 Correct 1111 ms 6184 KB Output is correct
17 Correct 552 ms 6720 KB Output is correct
18 Correct 517 ms 6852 KB Output is correct
19 Incorrect 666 ms 5972 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 3 ms 332 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 3 ms 356 KB Output is correct
10 Correct 4 ms 332 KB Output is correct
11 Correct 581 ms 648 KB Output is correct
12 Correct 556 ms 624 KB Output is correct
13 Correct 195 ms 664 KB Output is correct
14 Correct 160 ms 548 KB Output is correct
15 Correct 289 ms 460 KB Output is correct
16 Correct 236 ms 560 KB Output is correct
17 Correct 234 ms 460 KB Output is correct
18 Correct 129 ms 520 KB Output is correct
19 Correct 298 ms 572 KB Output is correct
20 Correct 233 ms 524 KB Output is correct
21 Correct 1944 ms 4324 KB Output is correct
22 Correct 1918 ms 6200 KB Output is correct
23 Correct 868 ms 6204 KB Output is correct
24 Correct 987 ms 6184 KB Output is correct
25 Correct 1096 ms 6244 KB Output is correct
26 Correct 1111 ms 6184 KB Output is correct
27 Correct 552 ms 6720 KB Output is correct
28 Correct 517 ms 6852 KB Output is correct
29 Incorrect 666 ms 5972 KB Output isn't correct
30 Halted 0 ms 0 KB -