oj.uz

Submission #130370

# Submission time Handle Problem Language Result Execution time Memory
130370 2019-07-15T04:47:03 Z 김세빈(#3148) Fence (CEOI08_fence) C++14
100 / 100
 45 ms 504 KB 
#include <bits/stdc++.h>

#define pcomp(p) ([&](point &pa, point &pb) { return ccw((p), pa, pb) > 0; })

using namespace std;

struct point{
	int x, y, t;
	point() {}
	point(int x, int y, int t) : x(x), y(y), t(t) {}
};

struct fenwick{
	int T[333];
	void addval(int p, int v) { for(; p<=300; p+=p&-p) T[p] += v; }
	int getval(int p) { return p? getval(p - (p & -p)) + T[p] : 0; }
};

fenwick T;
int D[222][222];
int n, m, ans;

int ccw(point &pa, point &pb, point &pc)
{
	return (pa.x * pb.y + pb.x * pc.y + pc.x * pa.y) -
		(pa.y * pb.x + pb.y * pc.x + pc.y * pa.x);
}

int calc(point &p, vector <point> &P)
{
	vector <point> X, Y;
	int i, j, k, v, t, ret;
	point q;
	
	sort(P.begin(), P.end(), pcomp(p));
	
	ret = 1e9;
	
	for(i=0; i<P.size(); i++){
		if(P[i].t) continue;
		
		X.clear(); Y.clear();
		
		for(j=0; j<i; j++){
			q = P[j];
			if(!q.t){
				q.t = j;
				X.push_back(q);
			}
		}
		
		sort(X.begin(), X.end(), pcomp(P[i]));
		
		for(j=i+1; j<P.size(); j++){
			q = P[j];
			if(q.t){
				T.addval(j, 1);
				q.t = -j;
			}
			else q.t = j;
			Y.push_back(q);
		}
		
		sort(Y.begin(), Y.end(), pcomp(P[i]));
		
		v = 40;
		
		for(j=0, k=0; j<Y.size(); j++){
			if(Y[j].t < 0){
				T.addval(-Y[j].t, -1);
				continue;
			}
			
			t = T.getval(Y[j].t);
			
			for(; k<X.size() && ccw(P[i], X[k], Y[j]) < 0; k++){
				v = min(v, D[X[k].t][i]);
			}
			
			D[i][Y[j].t] = v + 20 - t * 111;
			ret = min(ret, D[i][Y[j].t]);
		}
	}
	
	return ret;
}

int main()
{
	vector <point> P, V;
	int i, j, x, y;
	
	scanf("%d%d", &n, &m);
	
	for(i=0; i<n; i++){
		scanf("%d%d", &x, &y);
		P.emplace_back(x, y, 0);
	}
	
	for(i=0; i<m; i++){
		scanf("%d%d", &x, &y);
		P.emplace_back(x, y, 1);
	}
	
	sort(P.begin(), P.end(), [&](point &pa, point &pb){
		if(pa.x != pb.x) return pa.x < pb.x;
		else return pa.y < pb.y;
	});
	
	ans = 0;
	
	for(i=0; i<n+m; i++){
		if(P[i].t) continue;
		
		V.clear();
		
		for(j=i+1; j<n+m; j++){
			V.push_back(P[j]);
		}
		
		ans = min(ans, calc(P[i], V));
	}
	
	printf("%d\n", ans + m * 111);
	
	return 0;
}

Compilation message

fence.cpp: In function 'int calc(point&, std::vector<point>&)':
fence.cpp:39:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<P.size(); i++){
           ~^~~~~~~~~
fence.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i+1; j<P.size(); j++){
              ~^~~~~~~~~
fence.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, k=0; j<Y.size(); j++){
                 ~^~~~~~~~~
fence.cpp:76:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; k<X.size() && ccw(P[i], X[k], Y[j]) < 0; k++){
          ~^~~~~~~~~
fence.cpp: In function 'int main()':
fence.cpp:93: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:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~
fence.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 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 3 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 3 ms 376 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 488 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 25 ms 504 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #10
10.0 / 10.0

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