oj.uz

Submission #5970

# Submission time Handle Problem Language Result Execution time Memory
5970 2014-06-07T06:43:03 Z model_code Demarcation (BOI14_demarcation) C++
100 / 100
 126 ms 11384 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8216 KB Output is correct
2 Correct 0 ms 8216 KB Output is correct
3 Correct 0 ms 8216 KB Output is correct
4 Correct 3 ms 8216 KB Output is correct
5 Correct 0 ms 8216 KB Output is correct
6 Correct 0 ms 8216 KB Output is correct
7 Correct 0 ms 8216 KB Output is correct
8 Correct 3 ms 8216 KB Output is correct
9 Correct 46 ms 8216 KB Output is correct
10 Correct 0 ms 8216 KB Output is correct
11 Correct 3 ms 8216 KB Output is correct
12 Correct 3 ms 8216 KB Output is correct
13 Correct 3 ms 8216 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8216 KB Output is correct
2 Correct 0 ms 8216 KB Output is correct
3 Correct 3 ms 8216 KB Output is correct
4 Correct 0 ms 8216 KB Output is correct
5 Correct 0 ms 8216 KB Output is correct
6 Correct 0 ms 8216 KB Output is correct
7 Correct 0 ms 8216 KB Output is correct
8 Correct 3 ms 8216 KB Output is correct
9 Correct 0 ms 8216 KB Output is correct
10 Correct 0 ms 8216 KB Output is correct
11 Correct 3 ms 8216 KB Output is correct
12 Correct 0 ms 8216 KB Output is correct
13 Correct 0 ms 8216 KB Output is correct
14 Correct 3 ms 8216 KB Output is correct
15 Correct 0 ms 8216 KB Output is correct
16 Correct 0 ms 8216 KB Output is correct
17 Correct 0 ms 8216 KB Output is correct
18 Correct 0 ms 8216 KB Output is correct
19 Correct 0 ms 8216 KB Output is correct
20 Correct 0 ms 8216 KB Output is correct
21 Correct 0 ms 8216 KB Output is correct
22 Correct 3 ms 8216 KB Output is correct
23 Correct 0 ms 8216 KB Output is correct
24 Correct 3 ms 8216 KB Output is correct
25 Correct 0 ms 8216 KB Output is correct
26 Correct 0 ms 8216 KB Output is correct
27 Correct 0 ms 8216 KB Output is correct
28 Correct 3 ms 8216 KB Output is correct
29 Correct 0 ms 8216 KB Output is correct
30 Correct 0 ms 8216 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8216 KB Output is correct
2 Correct 0 ms 8216 KB Output is correct
3 Correct 3 ms 8216 KB Output is correct
4 Correct 0 ms 8216 KB Output is correct
5 Correct 0 ms 8216 KB Output is correct
6 Correct 0 ms 8216 KB Output is correct
7 Correct 3 ms 8216 KB Output is correct
8 Correct 0 ms 8216 KB Output is correct
9 Correct 0 ms 8216 KB Output is correct
10 Correct 0 ms 8216 KB Output is correct
11 Correct 0 ms 8216 KB Output is correct
12 Correct 0 ms 8216 KB Output is correct
13 Correct 3 ms 8216 KB Output is correct
14 Correct 3 ms 8216 KB Output is correct
15 Correct 3 ms 8216 KB Output is correct
16 Correct 0 ms 8216 KB Output is correct
17 Correct 3 ms 8216 KB Output is correct
18 Correct 0 ms 8216 KB Output is correct
19 Correct 3 ms 8216 KB Output is correct
20 Correct 0 ms 8216 KB Output is correct
21 Correct 0 ms 8216 KB Output is correct
22 Correct 0 ms 8216 KB Output is correct
23 Correct 3 ms 8216 KB Output is correct
24 Correct 0 ms 8216 KB Output is correct
25 Correct 0 ms 8216 KB Output is correct
26 Correct 0 ms 8216 KB Output is correct
27 Correct 3 ms 8216 KB Output is correct
28 Correct 0 ms 8216 KB Output is correct
29 Correct 0 ms 8216 KB Output is correct
30 Correct 3 ms 8216 KB Output is correct
31 Correct 0 ms 8216 KB Output is correct
32 Correct 0 ms 8216 KB Output is correct
33 Correct 3 ms 8216 KB Output is correct
34 Correct 3 ms 8216 KB Output is correct
35 Correct 0 ms 8216 KB Output is correct
36 Correct 0 ms 8216 KB Output is correct
37 Correct 0 ms 8216 KB Output is correct
38 Correct 0 ms 8216 KB Output is correct
39 Correct 0 ms 8216 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8216 KB Output is correct
2 Correct 3 ms 8216 KB Output is correct
3 Correct 3 ms 8216 KB Output is correct
4 Correct 3 ms 8216 KB Output is correct
5 Correct 3 ms 8216 KB Output is correct
6 Correct 3 ms 8216 KB Output is correct
7 Correct 0 ms 8216 KB Output is correct
8 Correct 0 ms 8216 KB Output is correct
9 Correct 46 ms 8216 KB Output is correct
10 Correct 3 ms 8216 KB Output is correct
11 Correct 0 ms 8216 KB Output is correct
12 Correct 0 ms 8216 KB Output is correct
13 Correct 0 ms 8216 KB Output is correct
14 Correct 3 ms 8216 KB Output is correct
15 Correct 0 ms 8216 KB Output is correct
16 Correct 0 ms 8216 KB Output is correct
17 Correct 0 ms 8216 KB Output is correct
18 Correct 0 ms 8216 KB Output is correct
19 Correct 0 ms 8216 KB Output is correct
20 Correct 0 ms 8216 KB Output is correct
21 Correct 0 ms 8216 KB Output is correct
22 Correct 3 ms 8216 KB Output is correct
23 Correct 0 ms 8216 KB Output is correct
24 Correct 3 ms 8216 KB Output is correct
25 Correct 0 ms 8216 KB Output is correct
26 Correct 3 ms 8216 KB Output is correct
27 Correct 0 ms 8216 KB Output is correct
28 Correct 3 ms 8216 KB Output is correct
29 Correct 0 ms 8216 KB Output is correct
30 Correct 0 ms 8216 KB Output is correct
31 Correct 0 ms 8216 KB Output is correct
32 Correct 3 ms 8216 KB Output is correct
33 Correct 0 ms 8216 KB Output is correct
34 Correct 3 ms 8216 KB Output is correct
35 Correct 3 ms 8216 KB Output is correct
36 Correct 3 ms 8216 KB Output is correct
37 Correct 0 ms 8216 KB Output is correct
38 Correct 3 ms 8216 KB Output is correct
39 Correct 3 ms 8216 KB Output is correct
40 Correct 0 ms 8216 KB Output is correct
41 Correct 0 ms 8216 KB Output is correct
42 Correct 3 ms 8216 KB Output is correct
43 Correct 0 ms 8348 KB Output is correct
44 Correct 29 ms 9536 KB Output is correct
45 Correct 39 ms 8216 KB Output is correct
46 Correct 23 ms 8216 KB Output is correct
47 Correct 9 ms 8216 KB Output is correct
48 Correct 9 ms 8876 KB Output is correct
49 Correct 73 ms 8348 KB Output is correct
50 Correct 29 ms 8348 KB Output is correct
51 Correct 49 ms 8216 KB Output is correct
52 Correct 126 ms 11384 KB Output is correct
53 Correct 76 ms 8348 KB Output is correct
54 Correct 76 ms 8216 KB Output is correct
55 Correct 29 ms 9536 KB Output is correct
56 Correct 53 ms 8216 KB Output is correct
57 Correct 86 ms 8216 KB Output is correct
58 Correct 89 ms 11384 KB Output is correct
59 Correct 93 ms 11384 KB Output is correct
60 Correct 29 ms 8216 KB Output is correct
61 Correct 9 ms 8216 KB Output is correct
62 Correct 16 ms 8216 KB Output is correct
63 Correct 26 ms 8216 KB Output is correct
64 Correct 16 ms 8216 KB Output is correct
65 Correct 33 ms 8216 KB Output is correct
66 Correct 46 ms 8216 KB Output is correct