Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 15:59:05
2018-05-26 15:40:53
2018-05-26 15:36:03
2018-05-26 15:35:37
2018-05-26 15:32:14
2018-05-26 15:22:59
2018-05-26 13:28:10
Task:Euclidean Geometry
Sender:Karhukopla
Submission time:2018-05-26 15:59:05
Status:READY
Result:WRONG ANSWER

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:3:11: warning: narrowing conversion of 'p.std::pair<int, int>::first' from 'int' to 'double' inside { } [-Wnarrowing]
 #define F first
           ^
input/code.cpp:22:24: note: in expansion of macro 'F'
     stack.push_back({p.F, p.S});
                        ^
input/code.cpp:4:11: warning: narrowing conversion of 'p.std::pair<int, int>::second' from 'int' to 'double' inside { } [-Wnarrowing]
 #define S second
           ^
input/code.cpp:22:29: note: in expansion of macro 'S'
     stack.push_back({p.F, p.S});
                             ^

Code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
int main() {
	int t;
	cin >> t;
	for (int ti = 0; ti < t; ++ti) {
		vector<pair<int, int>> ones;
		for (int i = 0; i < 100; ++i) {
			cin >> ws;
			for (int j = 0; j < 100; ++j) {
				char c;
				cin >> c;
				if (c == '1') ones.push_back({i, j});
			}
		}
		vector<complex<double>> stacks[2];
		for (int dir = 0; dir < 2; ++dir) {
			auto &stack = stacks[dir];
			for (auto p : ones) {
				stack.push_back({p.F, p.S});
				while (stack.size() >= 3) {
					bool drop = false;
					auto a = stack[stack.size()-3], b = stack[stack.size()-2], c = stack[stack.size()-1];
					double ang = arg((c-b)/(b-a));
					if (abs(ang) < M_PI/5) drop = true;
					else 
					if (dir ? (ang < 0) : (ang > 0)) {
						drop = true;
					}
					if (drop) {
						stack.pop_back();
						stack.pop_back();
						stack.push_back(c);
					} else {
						break;
					}
				}
			}
		}
		reverse(stacks[1].begin(), stacks[1].end());
		vector<complex<double>> fin;
		for (int dir = 0; dir < 2; ++dir) {
			for (auto c : stacks[dir]) {
				fin.push_back(c);
				while (fin.size() >= 2) {
					auto a = fin[fin.size()-2], b = fin[fin.size()-1];
					if (abs(a-b) <= 15) {
						fin.pop_back();
						fin.pop_back();
						fin.push_back(b);
					} else break;
				}
			}
		}
		if (abs(fin.front()-fin.back()) <= 15) {
			fin.pop_back();
		}
		int res = fin.size();
		if (res > 4) res = 4;
		if (res < 3) res = 3;
		cout << res << endl;
	}
}