# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
132441 |
2019-07-18T20:21:08 Z |
duality |
Fences (JOI18_fences) |
C++11 |
|
785 ms |
4472 KB |
#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-6
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);
}
bool comp2(point a,point b) {
if (abs(a.x-b.x) < EPS) return a.y < b.y-EPS;
else return a.x < b.x;
}
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 comp(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[22000];
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;
}
vector<pair<int,double> > adjList[44000];
int addEdge(point a,point b,int N,int c,int S,int f) {
int u = lower_bound(points,points+c,a,comp2)-points;
int v = lower_bound(points,points+c,b,comp2)-points;
if (check(a,b,S)) {
double d = f ? 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(1e9,1))) {
adjList[2*u].pb(mp(2*v+1,d)),adjList[2*u+1].pb(mp(2*v,d));
adjList[2*v].pb(mp(2*u+1,d)),adjList[2*v+1].pb(mp(2*u,d));
}
else {
adjList[2*u].pb(mp(2*v,d)),adjList[2*u+1].pb(mp(2*v+1,d));
adjList[2*v].pb(mp(2*u,d)),adjList[2*v+1].pb(mp(2*u+1,d));
}
}
return 0;
}
double dist[44000];
priority_queue<pair<double,int> > H;
double findDist(int s,int c) {
int i;
for (i = 0; i < 2*c; i++) dist[i] = 1e99;
dist[2*s] = 0,H.push(mp(0,2*s));
while (!H.empty()) {
int u = H.top().second;
double d = -H.top().first;
H.pop();
for (i = 0; i < adjList[u].size(); i++) {
int v = adjList[u][i].first;
if (d+adjList[u][i].second < dist[v]) {
dist[v] = d+adjList[u][i].second;
H.push(mp(-dist[v],v));
}
}
}
return dist[2*s+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,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 < N; i++) {
for (j = 0; j < N; j++) {
if (i != j) {
addEdge(s[i].a,closest(s[i].a,s[j]),N,c,S,0);
addEdge(s[i].b,closest(s[i].b,s[j]),N,c,S,0);
}
}
}
for (i = 0; i < N; i++) {
vector<point> v;
for (j = 0; j < c; j++) {
if (onSeg(points[j],s[i])) v.pb(points[j]);
}
sort(v.begin(),v.end(),comp2);
for (j = 1; j < v.size(); j++) addEdge(v[j-1],v[j],N,c,S,1);
}
double ans = 1e99;
for (i = 0; i < N; i++) {
ans = min(ans,findDist(lower_bound(points,points+c,s[i].a,comp2)-points,c));
ans = min(ans,findDist(lower_bound(points,points+c,s[i].b,comp2)-points,c));
}
printf("%.10lf\n",ans);
return 0;
}
Compilation message
fences.cpp: In function 'double findDist(int, int)':
fences.cpp:81:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i = 0; i < adjList[u].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~
fences.cpp: In function 'int main()':
fences.cpp:122:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (j = 1; j < v.size(); j++) addEdge(v[j-1],v[j],N,c,S,1);
~~^~~~~~~~~~
fences.cpp:94: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:95: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 time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
3 ms |
1400 KB |
Output is correct |
3 |
Correct |
3 ms |
1400 KB |
Output is correct |
4 |
Correct |
3 ms |
1400 KB |
Output is correct |
5 |
Correct |
3 ms |
1400 KB |
Output is correct |
6 |
Correct |
3 ms |
1400 KB |
Output is correct |
7 |
Correct |
3 ms |
1400 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1400 KB |
Output is correct |
10 |
Correct |
3 ms |
1400 KB |
Output is correct |
11 |
Correct |
3 ms |
1400 KB |
Output is correct |
12 |
Correct |
3 ms |
1400 KB |
Output is correct |
13 |
Correct |
3 ms |
1400 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
3 ms |
1400 KB |
Output is correct |
17 |
Correct |
3 ms |
1400 KB |
Output is correct |
18 |
Correct |
3 ms |
1400 KB |
Output is correct |
19 |
Correct |
3 ms |
1400 KB |
Output is correct |
20 |
Correct |
3 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
3 ms |
1400 KB |
Output is correct |
3 |
Correct |
3 ms |
1400 KB |
Output is correct |
4 |
Correct |
3 ms |
1400 KB |
Output is correct |
5 |
Correct |
3 ms |
1400 KB |
Output is correct |
6 |
Correct |
3 ms |
1400 KB |
Output is correct |
7 |
Correct |
3 ms |
1400 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1400 KB |
Output is correct |
10 |
Correct |
3 ms |
1400 KB |
Output is correct |
11 |
Correct |
3 ms |
1400 KB |
Output is correct |
12 |
Correct |
3 ms |
1400 KB |
Output is correct |
13 |
Correct |
3 ms |
1400 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
3 ms |
1400 KB |
Output is correct |
17 |
Correct |
3 ms |
1400 KB |
Output is correct |
18 |
Correct |
3 ms |
1400 KB |
Output is correct |
19 |
Correct |
3 ms |
1400 KB |
Output is correct |
20 |
Correct |
3 ms |
1400 KB |
Output is correct |
21 |
Correct |
3 ms |
1400 KB |
Output is correct |
22 |
Correct |
3 ms |
1404 KB |
Output is correct |
23 |
Correct |
3 ms |
1400 KB |
Output is correct |
24 |
Correct |
3 ms |
1400 KB |
Output is correct |
25 |
Correct |
3 ms |
1400 KB |
Output is correct |
26 |
Correct |
3 ms |
1400 KB |
Output is correct |
27 |
Correct |
3 ms |
1400 KB |
Output is correct |
28 |
Correct |
3 ms |
1400 KB |
Output is correct |
29 |
Correct |
3 ms |
1400 KB |
Output is correct |
30 |
Correct |
3 ms |
1400 KB |
Output is correct |
31 |
Correct |
3 ms |
1400 KB |
Output is correct |
32 |
Correct |
3 ms |
1400 KB |
Output is correct |
33 |
Correct |
3 ms |
1400 KB |
Output is correct |
34 |
Correct |
3 ms |
1400 KB |
Output is correct |
35 |
Correct |
3 ms |
1400 KB |
Output is correct |
36 |
Correct |
4 ms |
1400 KB |
Output is correct |
37 |
Correct |
3 ms |
1400 KB |
Output is correct |
38 |
Correct |
3 ms |
1400 KB |
Output is correct |
39 |
Correct |
3 ms |
1400 KB |
Output is correct |
40 |
Correct |
3 ms |
1400 KB |
Output is correct |
41 |
Correct |
3 ms |
1400 KB |
Output is correct |
42 |
Correct |
4 ms |
1400 KB |
Output is correct |
43 |
Correct |
3 ms |
1320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
3 ms |
1400 KB |
Output is correct |
3 |
Correct |
3 ms |
1400 KB |
Output is correct |
4 |
Correct |
3 ms |
1400 KB |
Output is correct |
5 |
Correct |
3 ms |
1400 KB |
Output is correct |
6 |
Correct |
3 ms |
1400 KB |
Output is correct |
7 |
Correct |
3 ms |
1400 KB |
Output is correct |
8 |
Correct |
3 ms |
1400 KB |
Output is correct |
9 |
Correct |
3 ms |
1400 KB |
Output is correct |
10 |
Correct |
3 ms |
1400 KB |
Output is correct |
11 |
Correct |
3 ms |
1400 KB |
Output is correct |
12 |
Correct |
3 ms |
1400 KB |
Output is correct |
13 |
Correct |
3 ms |
1400 KB |
Output is correct |
14 |
Correct |
3 ms |
1400 KB |
Output is correct |
15 |
Correct |
3 ms |
1400 KB |
Output is correct |
16 |
Correct |
3 ms |
1400 KB |
Output is correct |
17 |
Correct |
3 ms |
1400 KB |
Output is correct |
18 |
Correct |
3 ms |
1400 KB |
Output is correct |
19 |
Correct |
3 ms |
1400 KB |
Output is correct |
20 |
Correct |
3 ms |
1400 KB |
Output is correct |
21 |
Correct |
3 ms |
1400 KB |
Output is correct |
22 |
Correct |
3 ms |
1404 KB |
Output is correct |
23 |
Correct |
3 ms |
1400 KB |
Output is correct |
24 |
Correct |
3 ms |
1400 KB |
Output is correct |
25 |
Correct |
3 ms |
1400 KB |
Output is correct |
26 |
Correct |
3 ms |
1400 KB |
Output is correct |
27 |
Correct |
3 ms |
1400 KB |
Output is correct |
28 |
Correct |
3 ms |
1400 KB |
Output is correct |
29 |
Correct |
3 ms |
1400 KB |
Output is correct |
30 |
Correct |
3 ms |
1400 KB |
Output is correct |
31 |
Correct |
3 ms |
1400 KB |
Output is correct |
32 |
Correct |
3 ms |
1400 KB |
Output is correct |
33 |
Correct |
3 ms |
1400 KB |
Output is correct |
34 |
Correct |
3 ms |
1400 KB |
Output is correct |
35 |
Correct |
3 ms |
1400 KB |
Output is correct |
36 |
Correct |
4 ms |
1400 KB |
Output is correct |
37 |
Correct |
3 ms |
1400 KB |
Output is correct |
38 |
Correct |
3 ms |
1400 KB |
Output is correct |
39 |
Correct |
3 ms |
1400 KB |
Output is correct |
40 |
Correct |
3 ms |
1400 KB |
Output is correct |
41 |
Correct |
3 ms |
1400 KB |
Output is correct |
42 |
Correct |
4 ms |
1400 KB |
Output is correct |
43 |
Correct |
3 ms |
1320 KB |
Output is correct |
44 |
Correct |
785 ms |
4472 KB |
Output is correct |
45 |
Incorrect |
620 ms |
3928 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |