This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |