Submission #5970

#	Time	Username	Problem	Language	Result	Execution time	Memory
5970		model_code	Demarcation (BOI14_demarcation)	C++98	100 / 100	126 ms	11384 KiB

demarcation

#include <cstdio>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int Maxn = 100005;    // Max number of points
const int Maxe = 2 * Maxn;  // Max number of events
const int Maxr = 4;         // Max number of rotations

// Element in the set ("Line Sweep")
struct element {
	int y, ind, delt;
	element(int y = 0, int ind = 0, int delt = 0): y(y), ind(ind), delt(delt) {}
	bool operator <(const element &e) const {
		return y < e.y;
	}
};

// Event in "Line Sweep"
struct event {
	int x;
	element el;
	bool en;
	event(int x = 0, element el = element(), bool en = false): x(x), el(el), en(en) { }
	bool operator <(const event &e) const {
		if (x != e.x) return x < e.x;
		if (en != e.en) return en < e.en;
		return el.y < e.el.y;
	}
};

// "Candidate" split line
struct line {
	int x, y1, y2;
	line(int x = 0, int y1 = 0, int y2 = 0): x(x), y1(y1), y2(y2) {}
	bool operator <(const line &l) const {
		if (x != l.x) return x < l.x;
		if (y1 != l.y1) return y1 < l.y1;
		return y2 < l.y2;
	}
};

int n;               // Number of points
ii p[Maxn];          // Points of polygon
ll num[Maxn];        // Enumerated points by perimeter
event E[Maxe];       // Events in "Line Sweep"
int elen;
set <line> Spl;      // Can become split line
ii a[Maxn], b[Maxn]; // Candidates to compare
int alen, blen;      // Number of points of candidates

void Move(ii p[], int len, int &nil)
{
	nil = 0;
	for (int i = 0; i < len; i++)
		if (p[i] < p[nil]) nil = i;
	ii d = ii(-p[nil].first, -p[nil].second);
	if (d == ii(0, 0)) return;
	for (int i = 0; i < len; i++)
		p[i] = ii(p[i].first + d.first, p[i].second + d.second);
}

void Rotate(ii p[], int len)
{
	for (int i = 0; i < len; i++)
		p[i] = ii(p[i].second, -p[i].first);
}

void Reflect(ii p[], int len)
{
	for (int i = 0; i < len; i++)
		p[i].second = -p[i].second;
	reverse(p, p + len);
}

bool trivialCompare(ii a[], int alen, int anil, ii b[], int blen, int bnil)
{
	for (int i = 0; i < alen; i++) // alen = blen
		if (a[(anil + i) % alen] != b[(bnil + i) % blen])
			return false;
	return true;
}

bool spinAround(ii a[], int alen, int anil, ii b[], int blen)
{
	int bnil;   // The leftmost (the lowest) point
	for (int i = 0; i < Maxr; i++) {
		Rotate(b, blen);
		Move(b, blen, bnil);
		if (trivialCompare(a, alen, anil, b, blen, bnil))
			return true;
	}
	return false;
}

bool complexCompare(ii a[], int alen, ii b[], int blen)
{
	if (alen != blen) return false;
	int anil;   // The leftmost (the lowest) point
	Move(a, alen, anil);
	if (spinAround(a, alen, anil, b, blen)) return true;
	Reflect(b, blen);
	return spinAround(a, alen, anil, b, blen);
}

ll crossProduct(ll ax, ll ay, ll bx, ll by) { return ax * by - ay * bx; }

ll inLine(ii a, ii b, ii c)
{
	return crossProduct(b.first - a.first, b.second - a.second, 
						c.first - a.first, c.second - a.second) == 0;
}

void addPoint(ii p[], int &len, ii toadd)
{
	if (len == 0) p[len++] = toadd;
	else if (toadd != p[len - 1]) {
			if (len >= 2 && inLine(p[len - 2], p[len - 1], toadd))
				len--;
			p[len++] = toadd;
		}

}

void Construct(ii p[], int len, ii a[], int &alen, int s1, int s2, int x, int y1, int y2)
{
	alen = 0;
	addPoint(a, alen, ii(x, y1));
	int pnt = s1;
	do {
		pnt = (pnt + 1) % len;
		addPoint(a, alen, p[pnt]);
	} while (pnt != s2);
	addPoint(a, alen, ii(x, y2));
	if (alen >= 3 && inLine(a[alen - 2], a[alen - 1], a[0]))
		alen--;
	if (alen >= 3 && inLine(a[alen - 1], a[0], a[1])) {
		alen--;
		for (int i = 0; i < alen; i++)
			a[i] = a[i + 1];
	}
}

void Split(ii p[], int len, int x, int y1, int y2, ii a[], int &alen, ii b[], int &blen)
{
	int s1 = 0;
	while (!(p[s1].second == y1 && p[(s1 + 1) % len].second == y1 && 
		   p[(s1 + 1) % len].first <= x && x <= p[s1].first))
		s1 = (s1 + 1) % len;
	int s2 = 0;
	while (!(p[s2].second == y2 && p[(s2 + 1) % len].second == y2 && 
		   p[s2].first <= x && x <= p[(s2 + 1) % len].first))
		s2 = (s2 + 1) % len;
	Construct(p, len, a, alen, s1, s2, x, y1, y2); 
	Construct(p, len, b, blen, s2, s1, x, y2, y1);
}

void insertEvents(ii p[], int y, int a, int b, int delt)
{
	element el = element(y, a, delt);
	E[elen++] = event(p[a].first, el, false);
	E[elen++] = event(p[b].first, el, true);
}

ll getId(ll num[], const element &el, int curx)
{
	return num[el.ind] + el.delt * (curx - p[el.ind].first);
}

int canGrow(ii p[], int len, const element &el, int curx)
{
	int pi = (el.ind - 1 + len) % len;
	int ni = (el.ind + 1) % len;
	return (el.delt == 1? p[ni].first: p[pi].first) - curx;
}

bool getNear(const element &el, set <element> &S, set <element>::iterator &it)
{
	it = S.find(el);
	if (el.delt == 1)
		if (it == S.begin()) return false;
		else it--;
	else {
		it++;
		if (it == S.end()) return false;
	}
	return el.delt != it->delt;
}

void solveFor(const element &el, set <element> &S, ll num[], ii p[], int len, int curx, set <line> &Spl, bool hardcomp)
{
	set <element>::iterator it;
	if (!getNear(el, S, it)) return; 

	ll id1 = getId(num, el, curx);
	ll id2 = getId(num, *it, curx);
	int cangrow = min(canGrow(p, len, el, curx), canGrow(p, len, *it, curx));
	ll did = el.delt == 1? id1 - id2: id2 - id1;
	if (did < 0) did += num[len];

	ll grow = (num[len] / 2 - did) / 2;
	if ((!hardcomp && grow >= 0 || grow > 0) && grow <= cangrow && 2 * (did + 2 * grow) == num[len])
		Spl.insert(line(curx + grow, min(el.y, it->y), max(el.y, it->y)));
}

bool getVerticalSplit(ii p[], int len, int &x, int &y1, int &y2)
{
	// Prepare perimeter
	num[0] = 0;
	for (int i = 1; i <= len; i++)
		num[i] = num[i - 1] + abs(p[i % len].first - p[i - 1].first) + 
							  abs(p[i % len].second - p[i - 1].second);
	// Prepare events
	elen = 0;
	for (int i = 0; i < len; i++) {
		int ni = (i + 1) % len;
		if (p[i].second == p[ni].second)
			if (p[i].first < p[ni].first)
				insertEvents(p, p[i].second, i, ni, 1);
			else insertEvents(p, p[i].second, ni, i, -1);
	}
	sort(E, E + elen);
	// Line Sweep
	set <element> S;
	for (int i = 0, j; i < elen; i = j) {
		j = i;
		int curx = E[i].x;
		if (!Spl.empty()) curx = min(curx, Spl.begin()->x);

		while (j < elen && curx == E[j].x && !E[j].en) {
			S.insert(E[j].el);
			solveFor(E[j].el, S, num, p, len, curx, Spl, false);
			j++;
		}

		set <line>::iterator it = Spl.begin();
		while (it != Spl.end() && curx == it->x) {
			set <element>::iterator it2 = S.lower_bound(element(it->y1, 0, 0));
			if (it2 == S.end() || it2->y != it->y1) { Spl.erase(it++); continue; }
			it2++;
			if (it2 == S.end() || it2->y != it->y2) { Spl.erase(it++); continue; }
			Split(p, len, it->x, it->y1, it->y2, a, alen, b, blen);
			if (complexCompare(a, alen, b, blen)) {
				x = it->x; y1 = it->y1; y2 = it->y2;
				return true;
			}
			Spl.erase(it++);
		}

		while (j < elen && curx == E[j].x) {
			set <element>::iterator it = S.find(E[j].el);
			S.erase(it++);
			if (it != S.end())
				solveFor(*it, S, num, p, len, curx, Spl, true);
			j++;
		}
	}
	return false;
}

void Init()
{
	scanf("%d", &n);
	int lm = 0; // leftmost
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &p[i].first, &p[i].second);
		if (p[i] < p[lm]) lm = i;
	}
	if (!(p[lm].second < p[(lm + 1) % n].second))
		reverse(p, p + n); // Make clockwise
}

int main()
{
	Init();
	int x, y1, y2;
	if (getVerticalSplit(p, n, x, y1, y2))
		printf("%d %d %d %d\n", x, y1, x, y2);
	else {
		Rotate(p, n);
		if (getVerticalSplit(p, n, x, y1, y2))
			printf("%d %d %d %d\n", -y2, x, -y1, x); // Rotating back
		else printf("NO\n");
	}
	return 0;
}

Compilation message (stderr)

demarcation.cpp: In function 'void solveFor(const element&, std::set<element>&, ll*, ii*, int, int, std::set<line>&, bool)':
demarcation.cpp:206:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  if ((!hardcomp && grow >= 0 || grow > 0) && grow <= cangrow && 2 * (did + 2 * grow) == num[len])
                 ^
demarcation.cpp: In function 'bool getVerticalSplit(ii*, int, int&, int&, int&)':
demarcation.cpp:221:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
   if (p[i].second == p[ni].second)
      ^
demarcation.cpp: In function 'void Init()':
demarcation.cpp:267:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
demarcation.cpp:270:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p[i].first, &p[i].second);
                                            ^

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