oj.uz

Submission #56649

# Submission time Handle Problem Language Result Execution time Memory
56649 2018-07-12T05:24:25 Z ksun48 Fences (JOI18_fences) C++14
51 / 100
 1000 ms 6688 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double T;

const double PI = 3.1415926535;
const double EPS = 0.0000001;
struct P {
	T x, y;
	P() : x(0), y(0){}
	P(T x, T y) : x(x), y(y) {}
	P operator +(P p){
		return P(x+p.x,y+p.y);
	}
	P operator -(P p){
		return P(x-p.x,y-p.y);
	}
	P operator *(T t){
		return P(x*t, y*t);
	}
	P operator /(T t){
		return P(x,y) * (1.0/t);
	}
	T dist(){
		return sqrt(x*x+y*y);
	}
	T angle(){
		return atan2(y,x);
	}
	P rotate(T angle){
		double c = cos(angle);
		double s = sin(angle);
		return P(c*x-s*y,s*x+c*y);
	}
};
double get(){
	double r;
	cin >> r;
	r += (double)((rand() % 2000) - 1000) / 20000000.0;
	return r;
}
double ang;
int wind(P a1, P b1){
	// 0, 1, -1 if it crosses y = tan(ang) * x
	P a = a1.rotate(-ang);
	P b = b1.rotate(-ang);
	if((a-b).dist() < EPS) return 0;
	if(a.y > 0 && b.y > 0) return 0;
	if(a.y < 0 && b.y < 0) return 0;
	double nx = a.x + (0.0 - a.y) / (b.y - a.y) * (b.x - a.x);
	if(nx < 0) return 0;
	if(a.y < b.y) return 1;
	return -1;
}
double S;
int bad(P a, P b){
	// check if this intersects
	// [-S, S] cross S
	a.y -= S;
	b.y -= S;
	if((a-b).dist() < EPS) return 0;
	if(a.y > 0 && b.y > 0) return 0;
	if(a.y < 0 && b.y < 0) return 0;
	double nx = a.x + (0.0 - a.y) / (b.y - a.y) * (b.x - a.x);
	return (nx >= -S) && (nx <= S);
}
int ok(P a, P b){
	if(bad(a.rotate(0),b.rotate(0))) return 0;
	if(bad(a.rotate(PI/2.0), b.rotate(PI/2.0))) return 0;
	if(bad(a.rotate(2.0*PI/2.0), b.rotate(2.0*PI/2.0))) return 0;
	if(bad(a.rotate(3.0*PI/2.0), b.rotate(3.0*PI/2.0))) return 0;
	return 1;
}
double dot(P a, P b){
	return a.x*b.x + a.y*b.y;
}
int main(){
	ang = 0.001;
	int n;
	cin >> n >> S;
	vector<pair<P,P> > segs;
	vector<pair<int,int> > idx;
	for(int i = 0; i < n; i++){
		P a, b;
		a.x = get(); a.y = get(); b.x = get(); b.y = get();
		segs.push_back({a,b});
	}
	segs.push_back({P(S,S),P(S,S)});
	segs.push_back({P(S,-S),P(S,-S)});
	segs.push_back({P(-S,S),P(-S,S)});
	segs.push_back({P(-S,-S),P(-S,-S)});
	S -= 0.0001;
	// get from each point to each other point with nonzero winding number.
	// winding number adds one when 
	P origin = P(0,0);
	vector<P> pts;
	for(int i = 0; i < segs.size(); i++){
		idx.push_back({pts.size(), pts.size()+1});
		pts.push_back(segs[i].first);
		pts.push_back(segs[i].second);
	}
	vector<pair<int,int> > edges;
	vector<int> winds;
	vector<double> length;
	for(int i = 0; i < pts.size(); i++){
		for(int j = 0; j < pts.size(); j++){
			if( !ok(pts[i], pts[j]) ) continue;
			edges.push_back({i,j});
			winds.push_back( wind(pts[i],pts[j]) );
			length.push_back((pts[i]-pts[j]).dist());
		}
	}
	for(int i = 0; i < pts.size(); i++){
		for(int j = 0; j < segs.size(); j++){
			P p1 = segs[j].first - pts[i];
			P p2 = segs[j].second - pts[i];
			if((p1-p2).dist() < EPS) continue;
			double len = dot(p2-p1, origin-p1) / (p2-p1).dist();
			P r = p1 + (p2 - p1) * (len) / (p2-p1).dist();
			if((p1-r).dist() + (p2-r).dist() > (p1-p2).dist() + EPS){
				continue;
			}
			if( !ok(pts[i], pts[i] + r) ) continue;
			double cost = r.dist();
			edges.push_back({i,idx[j].first});
			winds.push_back( wind(pts[i], pts[i] + r) + wind(pts[i] + r, pts[idx[j].first]) );
			length.push_back(cost);

			edges.push_back({idx[j].first, i});
			winds.push_back( -winds[winds.size()-1] );
			length.push_back(cost);
		}
	}
	for(int i = 0; i < segs.size(); i++){
		assert(ok(segs[i].first, segs[i].second));
		edges.push_back({idx[i].first, idx[i].second});
		winds.push_back(wind(segs[i].first, segs[i].second));
		length.push_back(0.0);
		edges.push_back({idx[i].second, idx[i].first});
		winds.push_back(wind(segs[i].second, segs[i].first));
		length.push_back(0.0);
	}
	/*for(int i = 0; i < pts.size(); i++){
		cout << i << " " << pts[i].x << " " << pts[i].y << '\n';
	}
	cout << '\n';
	for(int i = 0; i < edges.size(); i++){
		cout << edges[i].first << " " << edges[i].second << " " << winds[i] << " " << length[i] << '\n';
	}*/
	int maxw = 5;
	int N = pts.size() * maxw;

	vector<pair<int,double> > realedges[N];
	for(int i = 0; i < edges.size(); i++){
		for(int r = 0; r < maxw; r++){
			int w = winds[i];
			if(w + r < 0 || w + r >= maxw) continue;
			realedges[edges[i].first * maxw + r].push_back({edges[i].second * maxw + w + r, length[i]});
			//double &v = dist[edges[i].first * maxw + r][edges[i].second * maxw + w + r];
			//v = min(v, length[i]);
		}
	}
	// 100 * 1500
	double ans = 20000.0;
	for(int q = 0; q < pts.size(); q++){
		double dist[N];
		int vis[N];
		set<pair<double, int> > z;
		for(int i = 0; i < N; i++){
			if(i != q * maxw){
				dist[i] = 200000000000.0;
			} else {
				dist[i] = 0;
			}
			vis[i] = 0;
			z.insert({dist[i], i});
		}
		while(!z.empty()){
			auto x = *z.begin();
			z.erase(z.begin());
			vis[x.second] = 1;
			for(int r = 0; r < realedges[x.second].size(); r++){
				double newdist = x.first + realedges[x.second][r].second;
				int loc = realedges[x.second][r].first;
				if(vis[loc]) continue;
				if(newdist < dist[loc]){
					z.erase({dist[loc],loc});
					dist[loc] = newdist;
					z.insert({dist[loc],loc});
				}
			}
		}
		ans = min(ans, dist[q * maxw + 1]);
	}
	printf("%.10lf\n", ans);
}

Compilation message

fences.cpp: In function 'int main()':
fences.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < segs.size(); i++){
                 ~~^~~~~~~~~~~~~
fences.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++){
                 ~~^~~~~~~~~~~~
fences.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < pts.size(); j++){
                  ~~^~~~~~~~~~~~
fences.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++){
                 ~~^~~~~~~~~~~~
fences.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < segs.size(); j++){
                  ~~^~~~~~~~~~~~~
fences.cpp:134:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < segs.size(); i++){
                 ~~^~~~~~~~~~~~~
fences.cpp:154:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edges.size(); i++){
                 ~~^~~~~~~~~~~~~~
fences.cpp:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int q = 0; q < pts.size(); q++){
                 ~~^~~~~~~~~~~~
fences.cpp:182:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int r = 0; r < realedges[x.second].size(); r++){
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 3 ms 528 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 3 ms 680 KB Output is correct
9 Correct 3 ms 744 KB Output is correct
10 Correct 3 ms 744 KB Output is correct
11 Correct 2 ms 744 KB Output is correct
12 Correct 2 ms 744 KB Output is correct
13 Correct 2 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 2 ms 744 KB Output is correct
16 Correct 3 ms 744 KB Output is correct
17 Correct 2 ms 744 KB Output is correct
18 Correct 3 ms 744 KB Output is correct
19 Correct 3 ms 744 KB Output is correct
20 Correct 3 ms 744 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 3 ms 528 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 3 ms 680 KB Output is correct
9 Correct 3 ms 744 KB Output is correct
10 Correct 3 ms 744 KB Output is correct
11 Correct 2 ms 744 KB Output is correct
12 Correct 2 ms 744 KB Output is correct
13 Correct 2 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 2 ms 744 KB Output is correct
16 Correct 3 ms 744 KB Output is correct
17 Correct 2 ms 744 KB Output is correct
18 Correct 3 ms 744 KB Output is correct
19 Correct 3 ms 744 KB Output is correct
20 Correct 3 ms 744 KB Output is correct
21 Correct 2 ms 744 KB Output is correct
22 Correct 4 ms 744 KB Output is correct
23 Correct 4 ms 744 KB Output is correct
24 Correct 3 ms 744 KB Output is correct
25 Correct 5 ms 744 KB Output is correct
26 Correct 4 ms 744 KB Output is correct
27 Correct 4 ms 744 KB Output is correct
28 Correct 4 ms 744 KB Output is correct
29 Correct 3 ms 744 KB Output is correct
30 Correct 4 ms 744 KB Output is correct
31 Correct 4 ms 744 KB Output is correct
32 Correct 4 ms 744 KB Output is correct
33 Correct 5 ms 744 KB Output is correct
34 Correct 5 ms 744 KB Output is correct
35 Correct 4 ms 744 KB Output is correct
36 Correct 5 ms 744 KB Output is correct
37 Correct 4 ms 744 KB Output is correct
38 Correct 3 ms 744 KB Output is correct
39 Correct 5 ms 744 KB Output is correct
40 Correct 2 ms 744 KB Output is correct
41 Correct 2 ms 744 KB Output is correct
42 Correct 3 ms 744 KB Output is correct
43 Correct 4 ms 744 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 3 ms 528 KB Output is correct
6 Correct 3 ms 552 KB Output is correct
7 Correct 2 ms 680 KB Output is correct
8 Correct 3 ms 680 KB Output is correct
9 Correct 3 ms 744 KB Output is correct
10 Correct 3 ms 744 KB Output is correct
11 Correct 2 ms 744 KB Output is correct
12 Correct 2 ms 744 KB Output is correct
13 Correct 2 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 2 ms 744 KB Output is correct
16 Correct 3 ms 744 KB Output is correct
17 Correct 2 ms 744 KB Output is correct
18 Correct 3 ms 744 KB Output is correct
19 Correct 3 ms 744 KB Output is correct
20 Correct 3 ms 744 KB Output is correct
21 Correct 2 ms 744 KB Output is correct
22 Correct 4 ms 744 KB Output is correct
23 Correct 4 ms 744 KB Output is correct
24 Correct 3 ms 744 KB Output is correct
25 Correct 5 ms 744 KB Output is correct
26 Correct 4 ms 744 KB Output is correct
27 Correct 4 ms 744 KB Output is correct
28 Correct 4 ms 744 KB Output is correct
29 Correct 3 ms 744 KB Output is correct
30 Correct 4 ms 744 KB Output is correct
31 Correct 4 ms 744 KB Output is correct
32 Correct 4 ms 744 KB Output is correct
33 Correct 5 ms 744 KB Output is correct
34 Correct 5 ms 744 KB Output is correct
35 Correct 4 ms 744 KB Output is correct
36 Correct 5 ms 744 KB Output is correct
37 Correct 4 ms 744 KB Output is correct
38 Correct 3 ms 744 KB Output is correct
39 Correct 5 ms 744 KB Output is correct
40 Correct 2 ms 744 KB Output is correct
41 Correct 2 ms 744 KB Output is correct
42 Correct 3 ms 744 KB Output is correct
43 Correct 4 ms 744 KB Output is correct
44 Execution timed out 1033 ms 6688 KB Time limit exceeded
45 Halted 0 ms 0 KB -