Submission #379579

#	Time	Username	Problem	Language	Result	Execution time	Memory
379579		pit4h	Fences (JOI18_fences)	C++14	100 / 100	896 ms	5944 KiB

fences

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
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());
	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));
	}
	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();
	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);

	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);
			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))) {
					cnt_inter++;
				}
				if(edge.intersect(Segment(-S, -S, S, -S))) {
					cnt_inter++;
				}
				if(edge.intersect(Segment(-S, S, S, S))) {
					cnt_inter++;
				}
				if(edge.intersect(Segment(S, -S, S, S))) {
					cnt_inter++;
				}
				if(cnt_inter > 0 && (cnt_inter != 2 || ((abs(p1.x) != S || abs(p1.y) != S) && (abs(p2.x) != S || abs(p2.y) != S)))) {
					continue;	
				}
			}
			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 it=0; it<n; ++it) {
		int i = -1;
		if(pts[it*2].x <= -S) i = it*2;
		if(pts[it*2+1].x <= -S) i = it*2+1;
		if(i==-1) 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)));
		
		while(pq.size()) {
			pii cur = pq.top().nd;
			pq.pop();
			if(vis[cur.st][cur.nd]) continue;	
			vis[cur.st][cur.nd] = 1;
			for(int j=0; j<m; ++j) {
				bool side = cur.nd;	
				if(half_change(pts[cur.st], edge_points[cur.st][j].st)) {
					side = !side;
				}
				if(half_change(edge_points[cur.st][j].st, edge_points[cur.st][j].nd)) {
					side = !side;
				}
				if(half_change(edge_points[cur.st][j].nd, pts[j])) {
					side = !side;
				}
				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 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49