oj.uz

Submission #348194

# Submission time Handle Problem Language Result Execution time Memory
348194 2021-01-14T10:49:07 Z lovro_nidogon1 Fence (CEOI08_fence) C++14
100 / 100
 4 ms 364 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct