Submission #658011

#	Time	Username	Problem	Language	Result	Execution time	Memory
658011		GusterGoose27	Demarcation (BOI14_demarcation)	C++11	0 / 100	7 ms	6996 KiB

demarcation

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

ll tot_area; // check that its even

pii operator*(int a, pii b) {
	return pii(b.first*a, b.second*a);
}
pii operator*(pii b, int a) {
	return pii(b.first*a, b.second*a);
}
pii operator+(pii a, pii b) {
	return pii(a.first+b.first, a.second+b.second);
}

ll operator*(pii a, pii b) {
	return (ll)a.first*b.second-(ll)a.second*b.first;
}

class poly;
bool cong(poly *a, poly *b);
typedef pair<poly*, poly*> ppp;
ppp merge(ppp a, ppp b, int t);
void pq_push(poly *a);
class poly {
public:
	pii pt1, pt2;
	pii normal;
	ll area = 0; // only for compressed
	bool dead = 0;
	int length;
	int turn; // 0 -> ccw, 1 -> cw, 2->straight
	poly *l = nullptr;
	poly *r = nullptr;
	ppp compressed = ppp(nullptr, nullptr); // actual polygon on this edge, head and tail
	poly(pii pt1, pii pt2, int turn, poly *l = nullptr, poly *r = nullptr, bool make_compress = 0) : pt1(pt1), pt2(pt2), l(l), r(r), turn(turn) {
		if (pt2.first > pt1.first) normal = pii(0, 1);
		if (pt2.second > pt1.second) normal = pii(-1, 0);
		if (pt2.first < pt1.first) normal = pii(0, -1);
		if (pt2.second < pt1.second) normal = pii(1, 0);
		length = abs(pt1.first-pt2.first)+abs(pt1.second-pt2.second);
		if (make_compress) {
			poly *np = new poly(pt1, pt2, 0);
			compressed = ppp(np, np);
		}
	}
	bool blocked() {
		return 0;
	}
	void fuse_next() {
		r->dead = 1;
		pt2 = r->pt2;
		length += r->length;
		turn = r->turn;
		if (r->r != nullptr) r->r->l = this;
		r = r->r;
	}
	void fuse_prev() {
		l->dead = 1;
		pt1 = l->pt1;
		length += l->length;
		if (l->l != nullptr) l->l->r = this;
		l = l->l;
	}
	void del() {
		dead = 1;
		if (l->turn != turn) {
			l->r = r;
			r->l = l;
			l->turn = 2;
		}
		else {
			assert(l->turn == 0 & turn == 0);
			if (l->length < r->length) {
				l->dead = 1;
				r->compressed = merge(l->compressed, r->compressed, 0);
				assert(l->l->turn == 1);
				l->l->turn = 0;
				l->l->r = r;
				r->l = l->l;
				r->length -= l->length;
				r->pt1 = l->pt1;
			}
			else {
				r->dead = 1;
				l->compressed = merge(l->compressed, r->compressed, 0);
				assert(r->turn == 1);
				l->turn = 0;
				l->r = r->r;
				r->r->l = l;
				l->length -= r->length;
				l->pt2 = r->pt2;
			}
		}
	}
	void straighten() {
		if (l->turn == 2) {
			compressed = merge(l->compressed, compressed, 2);
			fuse_prev();
		}
		if (turn == 2) {
			compressed = merge(compressed, r->compressed, 2);
			fuse_next();
		}
		pq_push(this);
	}
	void move(int d) {
		pii npt1 = pt1+normal*d;
		pii npt2 = pt2+normal*d;
		compressed.first = new poly(npt1, pt1, 0, nullptr, compressed.first);
		compressed.first->area = compressed.first->r->area;
		compressed.first->r->l = compressed.first;
		compressed.second = new poly(pt2, npt2, 1, compressed.second, nullptr);
		compressed.second->l->r = compressed.second;
		compressed.second->l->turn = 0;
		compressed.first->area += (ll) d*length;
		l->length -= d;
		r->length -= d;
		pt1 = npt1;
		pt2 = npt2;
		if (l->length == 0) l->del();
		if (r->length == 0) r->del();
	}
	bool compress() { // l is defined, r is defined, l->turn = turn = 0, no opposite direction edge "jutting out"
		// return 0 if nothing happens, return 1 if you find that this orientation has no equiareal, and exit if you find one
		int c_dist = min(l->length, r->length);
		ll ex_ar = (ll) c_dist*length;
		ll cur_ar = compressed.first->area;
		if (2*(cur_ar+ex_ar) >= tot_area) {
			ll req_ar = tot_area/2;
			if ((req_ar-cur_ar) % length != 0) return 1;
			move((req_ar-cur_ar)/length);
			compressed.second->turn = 0;
			compressed.second->r = new poly(pt2, pt1, 0, compressed.second, compressed.first);
			if (cong(this, compressed.first)) {
				cout << pt1.first << " " << pt1.second << " " << pt2.first << " " << pt2.second << "\n";
				exit(0);
			}
			return 1;
		}
		move(c_dist);
		straighten();
		return 0;
	}
};
class pq_node {
public:
	poly *rep;
	pii pt1;
	pii pt2;
	int length;
	pq_node(poly *r) : rep(r) {
		pt1 = r->pt1;
		pt2 = r->pt2;
		length = r->length;
	}
};
bool operator<(pq_node a, pq_node b) {
	return (a.length == b.length) ? (a.rep < b.rep) : (a.length > b.length);
}
priority_queue<pq_node> pq;
void pq_push(poly *a) {
	pq.push(pq_node(a));
}
ppp merge(ppp a, ppp b, int t) {
	a.first->area += b.first->area;
	a.second->r = b.first;
	b.first->l = a.second;
	a.second->turn = t;
	if (t == 2) {
		a.second->fuse_next();
	}
	return ppp(a.first, b.second);
}
bool cong(poly *a, poly *b) {
	return 1;
}

const int MAXN = 1e5;
pii points[MAXN];
poly *lines[MAXN];
int n;

void solve(bool orient) {
	priority_queue<pq_node>().swap(pq);
	for (int i = 0; i < n; i++) lines[i] = new poly(points[i], points[(i+1)%n], 0, nullptr, nullptr, 1);
	for (int i = 0; i < n; i++) {
		int j = (i+1)%n;
		lines[i]->turn = (lines[i]->normal*lines[j]->normal < 0);
		lines[i]->r = lines[j];
		lines[j]->l = lines[i];
	}
	for (int i = 0; i < n; i++)
		if (abs(lines[i]->normal.first) == orient && lines[i]->turn == 0 && lines[i]->l->turn == 0)
			pq_push(lines[i]);
	while (!pq.empty()) {
		pq_node pn = pq.top();
		pq.pop();
		if (pn.pt1 != pn.rep->pt1 || pn.pt2 != pn.rep->pt2 || pn.rep->dead) continue;
		if (pn.rep->compress()) return;
	}
	assert(false);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> points[i].first >> points[i].second;
	}
	tot_area = 0;
	for (int i = 0; i < n; i++) {
		tot_area += points[i]*points[(i+1)%n];
	}
	if (tot_area < 0) {
		for (int i = 0; i < n/2; i++) swap(points[i], points[n-1-i]);
		tot_area = -tot_area;
	}
	assert(tot_area % 2 == 0); tot_area /= 2;
	if (tot_area % 2 == 1) {
		cout << "NO\n";
		return 0;
	}
	solve(0);
	solve(1);
	cout << "NO\n";
}

Compilation message (stderr)

demarcation.cpp: In constructor 'poly::poly(pii, pii, int, poly*, poly*, bool)':
demarcation.cpp:37:8: warning: 'poly::r' will be initialized after [-Wreorder]
   37 |  poly *r = nullptr;
      |        ^
demarcation.cpp:35:6: warning:   'int poly::turn' [-Wreorder]
   35 |  int turn; // 0 -> ccw, 1 -> cw, 2->straight
      |      ^~~~
demarcation.cpp:39:2: warning:   when initialized here [-Wreorder]
   39 |  poly(pii pt1, pii pt2, int turn, poly *l = nullptr, poly *r = nullptr, bool make_compress = 0) : pt1(pt1), pt2(pt2), l(l), r(r), turn(turn) {
      |  ^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from demarcation.cpp:1:
demarcation.cpp: In member function 'void poly::del()':
demarcation.cpp:76:19: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   76 |    assert(l->turn == 0 & turn == 0);
      |           ~~~~~~~~^~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 15
• Subtask 3: 0 / 23
• Subtask 4: 0 / 50