Submission #448417

#	Time	Username	Problem	Language	Result	Execution time	Memory
448417		BERNARB01	Relay (COI16_relay)	C++17	37 / 100	1969 ms	4748 KiB

relay

#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 / 18
• Subtask 2: 19 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43