Submission #348194

#	Time	Username	Problem	Language	Result	Execution time	Memory
348194		lovro_nidogon1	Fence (CEOI08_fence)	C++14	100 / 100	4 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;
	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];
		while(ghull.size() > 1 and ccw(ghull[ghull.size() - 2], ghull[ghull.size() - 1], x)) ghull.pop_back();
		ghull.push_back(x);
		while(dhull.size() > 1 and !ccw(dhull[dhull.size() - 2], dhull[dhull.size() - 1], x)) 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 < 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]);
	}
	if(!gdot.size()) breturn cout << dot.size() * 111, 0;
	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;		
	}	
	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++) mi = min(mi, mat[i][i]);
	cout << (dot.size() - gdot.size()) * 111 + mi * 20;
}

Compilation message (stderr)

fence.cpp: In function 'int main()':
fence.cpp:26: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]
   26 |  for(int i = 0; i < ghull.size(); i++) hull.push_back(ghull[i]);
      |                 ~~^~~~~~~~~~~~~~
fence.cpp:27: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]
   27 |  for(int i = 0; i < dhull.size(); i++) hull.push_back(dhull[i]);
      |                 ~~^~~~~~~~~~~~~~
fence.cpp:28: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]
   28 |  for(int i = 0; i < dot.size(); i++) {
      |                 ~~^~~~~~~~~~~~
fence.cpp:30: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]
   30 |   for(int j = 1; j < hull.size(); j++) bad += ccw(hull[j - 1], hull[j], dot[i]);
      |                  ~~^~~~~~~~~~~~~
fence.cpp:36: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]
   36 |   for(int k = 0; k < gdot.size(); k++) bad += !ccw(kor[i], kor[j], gdot[k]);
      |                  ~~^~~~~~~~~~~~~

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