Submission #348160

#	Time	Username	Problem	Language	Result	Execution time	Memory
348160		lovro_nidogon1	Fence (CEOI08_fence)	C++14	10 / 100	2 ms	364 KiB

fence

#include<bits/stdc++.h>
#define breturn return 
using namespace std;
vector<pair<int, int> > kor, dhull, ghull, hull, dot, gdot;
int n, m, a, b, mat[101][101], mi;

bool ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	if(a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second) < 0) breturn false;
	else breturn true; 	
}
int main() {
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> a >> b;
		kor.push_back({a, b});
	}
	for(int i = 0; i < m; i++) {
		cin >> a >> b;
		dot.push_back({a, b});
	}
	sort(kor.begin(), kor.end());	
	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) mat[i][j] = 1e9;
	//for(int i = 0; i < n; i++) mat[i][i] = 0;
	ghull.push_back(kor[0]), ghull.push_back(kor[1]), dhull.push_back(kor[0]), dhull.push_back(kor[1]);
	for(int i = 2; i < n; i++) {
		pair<int, int> x = kor[i];
		if(!ccw(ghull[ghull.size() - 2], ghull[ghull.size() - 1], x)) ghull.push_back(x);
		else ghull.pop_back(), ghull.push_back(x);
		if(ccw(dhull[dhull.size() - 2], dhull[dhull.size() - 1], x)) dhull.push_back(x);
		else dhull.pop_back(), dhull.push_back(x);
	}
	dhull.pop_back();
	reverse(dhull.begin(), dhull.end());
	for(int i = 0; i < ghull.size(); i++) hull.push_back(ghull[i]);
	for(int i = 0; i < dhull.size(); i++) hull.push_back(dhull[i]);
//	for(int i = 0; i < hull.size(); i++) cout << hull[i].first << " . " << hull[i].second << '\n';
	for(int i = 0; i < dot.size(); i++) {
		bool bad = false;
		for(int j = 1; j < hull.size(); j++) bad += ccw(hull[j - 1], hull[j], dot[i]);
		if(!bad) gdot.push_back(dot[i]);
	}
//	for(int i = 0; i < gdot.size(); i++) cout << gdot[i].first << " -> " << gdot[i].second << '\n';

	for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i != j) {
		bool bad = false;
		for(int k = 0; k < gdot.size(); k++) {
			bad += ccw(kor[i], kor[j], gdot[k]);
		}
		if(!bad) mat[i][j] = 1, mat[j][i] = 1;		
	}	
	mi = (int)1e9;
	for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);	
//	for(int i = 0; i < n; i++, cout << '\n') for(int j = 0; j < n; j++) cout << mat[i][j] << " ";
	for(int i = 0; i < n; i++) mi = min(mi, mat[i][i]);
	cout << (dot.size() - gdot.size()) * 111 + (mi + 1) * 20;
}

Compilation message (stderr)

fence.cpp: In function 'int main()':
fence.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i = 0; i < ghull.size(); i++) hull.push_back(ghull[i]);
      |                 ~~^~~~~~~~~~~~~~
fence.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < dhull.size(); i++) hull.push_back(dhull[i]);
      |                 ~~^~~~~~~~~~~~~~
fence.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i < dot.size(); i++) {
      |                 ~~^~~~~~~~~~~~
fence.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for(int j = 1; j < hull.size(); j++) bad += ccw(hull[j - 1], hull[j], dot[i]);
      |                  ~~^~~~~~~~~~~~~
fence.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int k = 0; k < gdot.size(); k++) {
      |                  ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10