oj.uz

Submission #130371

# Submission time Handle Problem Language Result Execution time Memory
130371 2019-07-15T04:56:46 Z 구재현(#3156) Fence (CEOI08_fence) C++14
100 / 100
 3 ms 380 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

bool ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return dx1 * dy2 > dy1 * dx2;
}

int n, m;
pi a[105], b[105];
vector<pi> hull;

int adj[105][105];
int vis[105];

bool cmp(pi p, pi q){
	return ccw(a[0], p, q);
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++){
		scanf("%d %d",&a[i].first,&a[i].second);
	}
	for(int i=0; i<m; i++){
		scanf("%d %d",&b[i].first,&b[i].second);
	}
	swap(a[0], *min_element(a, a+n));
	sort(a+1, a+n, cmp);
	for(int i=0; i<n; i++){
		while(hull.size() >= 2 && !ccw(hull[hull.size()-2], hull.back(), a[i])){
			hull.pop_back();
		}
		hull.push_back(a[i]);
	}
	for(int i=0; i<hull.size(); i++){
		for(int j=0; j<m; j++){
			if(!ccw(hull[i], hull[(i+1)%hull.size()], b[j])){
				vis[j] = 1;
			}
		}
	}
	memset(adj,0x3f,sizeof(adj));
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(i == j) continue;
			adj[i][j] = 1;
			for(int k=0; k<m; k++){
				if(vis[k]) continue;
				if(!ccw(a[i], a[j], b[k])){
					adj[i][j] = 1e9;
					break;
				}
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
			}
		}
	}
	int cov = 1e9;
	for(int i=0; i<n; i++){
		cov = min(cov, adj[i][i]);
	}
	if(count(vis, vis + m, 1) == m){
		cov = 0;
	}
	printf("%d",cov * 20 + 111 * count(vis, vis + m, 1));
}

Compilation message

fence.cpp: In function 'int main()':
fence.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<hull.size(); i++){
               ~^~~~~~~~~~~~
fence.cpp:94:53: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::iterator_traits<int*>::difference_type {aka long int}' [-Wformat=]
  printf("%d",cov * 20 + 111 * count(vis, vis + m, 1));
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
fence.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
fence.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first,&a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&b[i].first,&b[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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