oj.uz

Submission #379577

# Submission time Handle Problem Language Result Execution time Memory
379577 2021-03-18T16:34:04 Z pit4h Fences (JOI18_fences) C++14
51 / 100
 1000 ms 5684 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define cerr if(0)cerr
using namespace std;
using ld = long double;
using pii = pair<int, int>;
const ld INF = 1e16+1, MAX_X = 201, eps = 1e-9;
const int MAXN = 205;
int n, S, m;

int sgn(ld x) {
	return (x>=0)? x? 1 : 0 : -1;
}

struct Segment;
struct Point {
	ld x, y;
	Point() {} Point(ld _x, ld _y) { x = _x, y = _y; }
	Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
	bool operator==(const Point& o) const { return (abs(x-o.x)<eps && abs(y-o.y)<eps); }
	
	ld cross(Point o) { return x*o.y - o.x*y; }
	ld cross(Point p1, Point p2) { return (p1 - *this).cross(p2 - *this); }
	ld dot(Point o) { return x * o.x + y * o.y; }
	ld dot(Point p1, Point p2) { return (p1 - *this).dot(p2 - *this); }

	ld dist(Point o) { return (ld)sqrt((x-o.x)*(x-o.x) + (y-o.y)*(y-o.y)); }
	ld dist(Segment* seg, Point& p2);
};
bool inter1d(ld a, ld b, ld c, ld d) {
	if(a > b) swap(a, b);
	if(c > d) swap(c, d);
	return max(a, c)-eps <= min(b, d);
}
struct Segment {
	Point a, b;
	Segment() {} Segment(ld _a, ld _b, ld _c, ld _d) { a = Point(_a, _b), b = Point(_c, _d); }
	Segment(Point _a, Point _b) { a = _a, b = _b; }
	bool operator!=(const Segment& o) const {
		return !((a==o.a && b==o.b) || (a==o.b && b==o.a));
	}
	ld length() { return a.dist(b); }
	ld dist(Segment o, Point& p1, Point& p2) {
		p1 = a;
		if(a == b && o.a == o.b) {
			p2 = o.a;
			return a.dist(o.a);
		}
		if(a==b) {
			return a.dist(&o, p2);
		}
		if(o.a==o.b) {
			p2 = o.a;
			return (o.a).dist(this, p1);
		}
		ld min_dist = a.dist(&o, p2);
		Point pp;
		if(b.dist(&o, pp) < min_dist) {
			p1 = b, min_dist = b.dist(&o, p2);
		}
		if((o.a).dist(this, pp) < min_dist) {
			p2 = o.a, min_dist = (o.a).dist(this, p1);
		}
		if((o.b).dist(this, pp) < min_dist) {
			p2 = o.b, min_dist = (o.b).dist(this, p1);
		}
		return min_dist;
	}
	bool intersect(Segment o) {
		//if(a == o.a || a == o.b || b == o.a || b == o.b) return false;
		if((o.a).cross(a, o.b)==0 && (o.a).cross(b, o.b)==0) {
			return inter1d(a.x, b.x, o.a.x, o.b.x) && inter1d(a.y, b.y, o.a.y, o.b.y);	
			//return false;
		}
		return sgn(a.cross(b, o.a)) != sgn(a.cross(b, o.b)) && sgn((o.a).cross(o.b, a)) != sgn((o.a).cross(o.b, b));
	}
};
ld Point::dist(Segment* seg, Point& p2) {
	ld height = abs(cross(seg->a, seg->b)) / (seg->length());
	//cerr<<"dist(): "<<(seg->a).x<<' '<<(seg->a).y<<' '<<(seg->b).x<<' '<<(seg->b).y<<"  "<<x<<' '<<y<<"  "<<height<<'\n';
	if((seg->a).dot(*this, seg->b) < (ld)0 || (seg->b).dot(*this, seg->a) < (ld)0) {
		if(dist(seg->a) < dist(seg->b)) p2 = seg->a;
		else p2 = seg->b;
		return min(dist(seg->a), dist(seg->b));
	}
	//cerr<<' '<<(seg->a).dot(*this, seg->b) / (seg->length())<<' '<<'\n';
	p2.x = seg->a.x + (seg->a).dot(*this, seg->b) / seg->length() * (seg->b.x - seg->a.x) / seg->length();			
	p2.y = seg->a.y + (seg->a).dot(*this, seg->b) / seg->length() * (seg->b.y - seg->a.y) / seg->length();
	cerr<<x<<' '<<y<<' '<<(seg->a).x<<' '<<(seg->a).y<<' '<<(seg->b).x<<' '<<(seg->b).y<<": "<<height<<'\n';
	return height;
}

bool half_change(Point p1, Point p2) {
	if(Segment(p1, p2).intersect(Segment(-S, S-eps, -S, MAX_X)) && ((p1.x <= -S && p2.x > -S) || (p1.x > -S && p2.x <= -S))) {
		return true;
	}
	return false;
}

ld w[2*MAXN][2*MAXN];
pair<Point, Point> edge_points[2*MAXN][2*MAXN];
inline void init();
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>S;
	init();
	vector<Segment> fence(n+4);
	vector<Point> pts;
	for(int i=0; i<n; ++i) {
		cin>>fence[i].a.x>>fence[i].a.y>>fence[i].b.x>>fence[i].b.y;
	}
	fence[n] = Segment(S, S, S, S);
	fence[n+1] = Segment(S, -S, S, -S);
	fence[n+2] = Segment(-S, S, -S, S);
	fence[n+3] = Segment(-S, -S, -S, -S);
	n = n+4;	

	for(int i=0; i<n; ++i) {
		pts.push_back(fence[i].a);
		pts.push_back(fence[i].b);
	}
	m = pts.size(); assert(m==2*n);

	/*Segment xd(5, 1, 7, 2);
	Point _p1, _p2;
	cerr<<Segment(-3, 5, 1, 8).dist(xd, _p1, _p2)<<"  "<<_p1.x<<' '<<_p1.y<<"  "<<_p2.x<<' '<<_p2.y<<'\n';
	return 0;*/

	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			Point p1, p2;
			ld dist = fence[i].dist(fence[j], p1, p2);
			Segment edge(p1.x, p1.y, p2.x, p2.y);
			cerr<<i<<' '<<j<<": "<<p1.x<<' '<<p1.y<<", "<<p2.x<<' '<<p2.y<<'\n';
			if(Segment(p1, p2) != Segment(-S, -S, -S, S) && Segment(p1, p2) != Segment(-S, -S, S, -S) && Segment(p1, p2) != Segment(-S, S, S, S) && Segment(p1, p2) != Segment(S, -S, S, S)) {
				int cnt_inter = 0;
				if(edge.intersect(Segment(-S, -S, -S, S))) {
					cerr<<"a ";
					cnt_inter++;
				}
				if(edge.intersect(Segment(-S, -S, S, -S))) {
					cerr<<"b ";
					cnt_inter++;
				}
				if(edge.intersect(Segment(-S, S, S, S))) {
					cerr<<"c ";
					cnt_inter++;
				}
				if(edge.intersect(Segment(S, -S, S, S))) {
					cerr<<"d ";
					cnt_inter++;
				}
				cerr<<'\n';
				if(cnt_inter > 0 && (cnt_inter != 2 || ((abs(p1.x) != S || abs(p1.y) != S) && (abs(p2.x) != S || abs(p2.y) != S)))) {
					continue;	
				}
			}
			cerr<<' '<<dist<<'\n';
			w[2*i][2*j] = w[2*i+1][2*j] = w[2*i][2*j+1] = w[2*i+1][2*j+1] = dist;
			if(i!=j) {
				edge_points[2*i][2*j] = edge_points[2*i+1][2*j] = edge_points[2*i][2*j+1] = edge_points[2*i+1][2*j+1] = mp(p1, p2);
			}
			else {
				edge_points[2*i][2*j] = mp(fence[i].a, fence[i].a);
				edge_points[2*i+1][2*j+1] = mp(fence[i].b, fence[i].b);
				edge_points[2*i][2*j+1] = mp(fence[i].a, fence[i].b);
				edge_points[2*i+1][2*j] = mp(fence[i].b, fence[i].a);
			}
		}
	}
	ld ans = INF;	
	for(int i=0; i<m; ++i) {
		if(pts[i].x > -S) continue;
		vector<vector<ld>> dist(m, vector<ld>(2, INF));
		vector<vector<bool>> vis(m, vector<bool>(2));
		dist[i][0] = 0;
		priority_queue<pair<ld, pii>> pq;
		pq.push(mp(0, mp(i, 0)));
		
		cerr<<"start: "<<i<<" - "<<pts[i].x<<' '<<pts[i].y<<'\n';
		while(pq.size()) {
			pii cur = pq.top().nd;
			pq.pop();
			if(vis[cur.st][cur.nd]) continue;	
			vis[cur.st][cur.nd] = 1;
			//if(i==0) cerr<<"pq: "<<cur.st<<' '<<cur.nd<<": "<<dist[cur.st][cur.nd]<<'\n';
			for(int j=0; j<m; ++j) {
				bool side = cur.nd;	
				//if(pts[j].y >= S && ((pts[j].x > -S && pts[cur.st].x <= -S) || (pts[j].x <= -S && pts[cur.st].x > -S))) {
				//if(Segment(pts[cur.st], pts[j]).intersect(Segment(-S, S, -S, MAX_X)) && ((pts[cur.st].x <= -S && pts[j].x > -S) || (pts[cur.st].x > -S && pts[j].x <= -S))) {
				if(half_change(pts[cur.st], edge_points[cur.st][j].st)) {
					//if(i==0 && j==1) cerr<<"hc "<<pts[cur.st].x<<' '<<pts[cur.st].y<<"  "<<edge_points[cur.st][j].st.x<<' '<<edge_points[cur.st][j].st.y<<'\n';
					side = !side;
				}
				if(half_change(edge_points[cur.st][j].st, edge_points[cur.st][j].nd)) {
					//if(i==0 && j==1) cerr<<"hc "<<edge_points[cur.st][j].st.x<<' '<<edge_points[cur.st][j].st.y<<"  "<<edge_points[cur.st][j].nd.x<<' '<<edge_points[cur.st][j].nd.y<<'\n';
					side = !side;
				}
				if(half_change(edge_points[cur.st][j].nd, pts[j])) {
					//if(i==0 && j==1) cerr<<"hc "<<edge_points[cur.st][j].nd.x<<' '<<edge_points[cur.st][j].nd.y<<"  "<<pts[j].x<<' '<<pts[j].y<<'\n';
					side = !side;
				}
				//if(i==0 && j==1) cerr<<' '<<j<<' '<<side<<' '<<w[cur.st][j]<<"  "<<pts[cur.st].x<<' '<<pts[cur.st].y<<", "<<pts[j].x<<' '<<pts[j].y<<' '<<edge_points[cur.st][j].nd.x<<' '<<edge_points[cur.st][j].nd.y<<' '<<half_change(edge_points[cur.st][j].nd, pts[j])<<'\n';
				if(dist[j][side]-eps > dist[cur.st][cur.nd] + w[cur.st][j]) {
					dist[j][side] = dist[cur.st][cur.nd] + w[cur.st][j];
					pq.push(mp(-dist[j][side], mp(j, side)));
				}
			}
		}
		
		ans = min(ans, dist[i][1]);
	}
	cout<<fixed<<setprecision(3)<<ans<<'\n';
}

inline void init() {
	for(int i=0; i<2*(n+4); ++i) {
		for(int j=0; j<2*(n+4); ++j) {
			w[i][j] = INF;
		}
	}
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct

Subtask #2
33.0 / 33.0

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

Subtask #3
0 / 49.0

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