Submission #132391

#TimeUsernameProblemLanguageResultExecution timeMemory
132391dualityFences (JOI18_fences)C++11
0 / 100
2 ms376 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back typedef long long int LLI; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii; #define x first #define y second #define point pair<double,double> #define EPS 1e-9 struct seg { point a,b; }; seg s[104]; bool comp(point a,point b) { return (abs(a.x-b.x) < EPS) && (abs(a.y-b.y) < EPS); } int ccw(point a,point b,point c) { return (b.x-a.x)*(c.y-a.y) > (b.y-a.y)*(c.x-a.x)+EPS; } point closest(point p,seg s) { if (s.a == s.b) return s.a; point a = s.a,b = s.b; point ap = mp(p.x-a.x,p.y-a.y),ab = mp(b.x-a.x,b.y-a.y); double f = (ap.x*ab.x+ap.y*ab.y)/(ab.x*ab.x+ab.y*ab.y); if (f < 0) return a; if (f > 1) return b; return mp((1-f)*a.x+f*b.x,(1-f)*a.y+f*b.y); } int onSeg(point p,seg s) { return closest(p,s) == p; } int inter(point a,point b,point c,point d) { if (comp(a,c) || comp(a,d) || comp(b,c) || comp(b,d)) return 0; else return (ccw(a,b,d) != ccw(a,b,c)) && (ccw(c,d,a) != ccw(c,d,b)); } point points[200]; double dist[400][400]; int check(point a,point b,int S) { if ((a.x > -S+EPS) && (a.x < S-EPS) && (a.y > -S+EPS) && (a.y < S-EPS)) return 0; if ((b.x > -S+EPS) && (b.x < S-EPS) && (b.y > -S+EPS) && (b.y < S-EPS)) return 0; if ((a.x+b.x > -2*S+EPS) && (a.x+b.x < 2*S-EPS) && (a.y+b.y > -2*S+EPS) && (a.y+b.y < 2*S-EPS)) return 0; if (inter(a,b,mp(S,S),mp(S,-S))) return 0; if (inter(a,b,mp(S,-S),mp(-S,-S))) return 0; if (inter(a,b,mp(-S,-S),mp(-S,S))) return 0; if (inter(a,b,mp(-S,S),mp(S,S))) return 0; return 1; } int main() { int i; int N,S; scanf("%d %d",&N,&S); for (i = 0; i < N; i++) scanf("%lf %lf %lf %lf",&s[i].a.x,&s[i].a.y,&s[i].b.x,&s[i].b.y); s[N] = (seg){mp(S,S),mp(S,S)}; s[N+1] = (seg){mp(S,-S),mp(S,-S)}; s[N+2] = (seg){mp(-S,S),mp(-S,S)}; s[N+3] = (seg){mp(-S,-S),mp(-S,-S)}; N += 4; int j,k,c = 0; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) points[c++] = closest(s[i].a,s[j]),points[c++] = closest(s[i].b,s[j]); } sort(points,points+c); c = unique(points,points+c,comp)-points; for (i = 0; i < 2*c; i++) fill(dist[i],dist[i]+2*c,1e99),dist[i][i] = 0; for (i = 0; i < c; i++) { for (j = i+1; j < c; j++) { point a = points[i],b = points[j]; for (k = 0; k < N; k++) { if (onSeg(a,s[k]) && onSeg(b,s[k])) break; } if (check(a,b,S)) { double d = (k < N) ? 0:sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); if (inter(a,b,mp(0,0),mp(1e5,1))) { dist[2*i][2*j+1] = dist[2*i+1][2*j] = d; dist[2*j][2*i+1] = dist[2*j+1][2*i] = d; } else { dist[2*i][2*j] = dist[2*i+1][2*j+1] = d; dist[2*j][2*i] = dist[2*j+1][2*i+1] = d; } } } } for (k = 0; k < 2*c; k++) { for (i = 0; i < 2*c; i++) { for (j = 0; j < 2*c; j++) dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]); } } double ans = 1e99; for (i = 0; i < c; i++) ans = min(ans,dist[2*i][2*i+1]); printf("%.10lf\n",ans); return 0; }

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&S);
     ~~~~~^~~~~~~~~~~~~~~
fences.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%lf %lf %lf %lf",&s[i].a.x,&s[i].a.y,&s[i].b.x,&s[i].b.y);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...