| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 132079 |
2019-07-18T09:36:46 Z |
onjo0127 |
Fences (JOI18_fences) |
C++11 |
|
30 ms |
23908 KB |
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pid = pair<int, double>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
#define X first
#define Y second
const double eps = 1e-6;
struct line { pdd S, E; };
struct dot { pdd D; int id; bool ps; };
struct node { double v; int c, id; };
bool operator <(node PP, node QQ) { return PP.v > QQ.v; }
inline double f(double x) { return max(x, -x); }
inline double dst(pdd A, pdd B) { return sqrt((A.X-B.X) * (A.X-B.X) + (A.Y-B.Y) * (A.Y-B.Y)); }
inline double CCW(pdd A, pdd B, pdd C) { return A.X*B.Y + B.X*C.Y + C.X*A.Y - A.Y*B.X - B.Y*C.X - C.Y*A.X; }
inline int CCWs(pdd A, pdd B, pdd C) {
double tmp = CCW(A, B, C);
if(f(tmp) < eps) return 0;
if(tmp < 0) return -1;
if(tmp > 0) return +1;
}
inline bool on(line A, pdd B) {
if(A.S > A.E) swap(A.S, A.E);
if(B < A.S || A.E < B) return false;
return f(CCW(A.S, A.E, B)) < eps;
}
inline bool its(line A, line B) { // strict
return CCWs(A.S, A.E, B.S) * CCWs(A.S, A.E, B.E) == -1 && CCWs(B.S, B.E, A.S) * CCWs(B.S, B.E, A.E) == -1;
}
inline pdd push(line A, pdd B) {
double ds = dst(A.S, A.E);
double d = f(CCW(A.S, A.E, B) / ds);
double dx = A.S.Y - A.E.Y, dy = A.E.X - A.S.X;
pdd PA = {B.X + dx * (d/ds), B.Y + dy * (d/ds)};
pdd PB = {B.X - dx * (d/ds), B.Y - dy * (d/ds)};
if(dst(PA, A.S) > dst(PB, A.S)) swap(PA, PB);
return PA;
}
line I = {{0.0, 0.0}, {1000.0, 1.0}};
vector<dot> T;
vector<pid> adj[1000009];
line A[111];
int N, S, K;
double ans = 1e9, D[2][1000009];
bool IT[40009][40009];
inline bool ok(line L) {
bool f = 0;
f |= its(L, {{S, S}, {-S, -S}});
f |= its(L, {{-S, S}, {S, -S}});
return !f;
}
void dijk(int st) {
// printf("start: (%d, %d)\n", T[st].D.X, T[st].D.Y);
vector<pii> rec = {{0, st}};
D[0][st] = 0.0;
priority_queue<node> pq; pq.push({0.0, 0, st});
while(pq.size()) {
node n = pq.top(); pq.pop();
if((n.id == st && n.c == 1) || n.v > ans) break;
// printf("now: (%f, %d, (%d, %d))\n", n.v, n.c, T[n.id].D.X, T[n.id].D.Y);
if(f(D[n.c][n.id] - n.v) > eps) continue;
for(auto& it: adj[n.id]) {
int tc = n.c;
if(IT[n.id][it.X]) tc = 1 - tc;
if(D[tc][it.X] > n.v + it.Y) {
D[tc][it.X] = n.v + it.Y;
rec.push_back({tc, it.X});
pq.push({D[tc][it.X], tc, it.X});
}
}
}
ans = min(ans, D[1][st]);
for(auto& it: rec) D[it.X][it.Y] = 1e9;
}
void make_edge(int u, int v, double c) {
adj[u].push_back({v, c});
adj[v].push_back({u, c});
}
int main() {
scanf("%d%d",&N,&S);
// N = 100; S = 100;
ans = 8.0*S;
for(int i=1; i<=N; i++) {
scanf("%lf%lf%lf%lf", &A[i].S.X, &A[i].S.Y, &A[i].E.X, &A[i].E.Y);
// A[i].S = {i, 100}; A[i].E = {i+1, 100};
T.push_back({A[i].S, i, 0});
T.push_back({A[i].E, i, 0});
}
T.push_back({{S, S}, N+1, 0});
T.push_back({{S, -S}, N+2, 0});
T.push_back({{-S, -S}, N+3, 0});
T.push_back({{-S, S}, N+4, 0});
int L = T.size();
for(int i=1; i<=N; i++) {
make_edge(2*i-2, 2*i-1, 0);
for(int j=0; j<T.size(); j++) {
if(i == T[j].id) continue;
pdd pu = push(A[i], T[j].D);
double dp = dst(pu, T[j].D), ds = dst(T[j].D, A[i].S), de = dst(T[j].D, A[i].E);
if(!ok({T[j].D, pu}) || !on(A[i], pu)) dp = 1e9;
if(!ok({T[j].D, A[i].S})) ds = 1e9;
if(!ok({T[j].D, A[i].E})) de = 1e9;
double d = min({ds, de, dp});
if(d == 1e9) continue;
make_edge(j, 2*i-2, d);
}
}
for(int i=2*N; i<2*N+4; i++) {
for(int j=i+1; j<2*N+4; j++) {
if(!ok({T[i].D, T[j].D})) continue;
make_edge(i, j, dst(T[i].D, T[j].D));
}
}
K = T.size();
for(int i=0; i<K; i++) {
for(int j=i+1; j<K; j++) {
if(its({T[i].D, T[j].D}, I)) IT[i][j] = IT[j][i] = 1;
}
}
// printf("K: %d\n", K);
// for(auto& it: T) {
// printf("position(%f, %f), id: %d, pushed?: %d\n", it.D.X, it.D.Y, it.id, it.ps);
// }
srand(14341);
for(int i=0; i<K; i++) D[0][i] = D[1][i] = 1e9;
for(int i=0; i<2*N; i+=2) dijk(i);
for(int i=2*N; i<2*N+4; i++) dijk(i);
printf("%.10f", ans);
return 0;
}
Compilation message
fences.cpp: In function 'int main()':
fences.cpp:109:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0; j<T.size(); j++) {
~^~~~~~~~~
fences.cpp:105:6: warning: unused variable 'L' [-Wunused-variable]
int L = T.size();
^
fences.cpp:91:7: 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:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lf%lf%lf%lf", &A[i].S.X, &A[i].S.Y, &A[i].E.X, &A[i].E.Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fences.cpp: In function 'int CCWs(pdd, pdd, pdd)':
fences.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
26 ms |
23908 KB |
Output is correct |
| 3 |
Correct |
30 ms |
23864 KB |
Output is correct |
| 4 |
Correct |
27 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
25 ms |
23800 KB |
Output is correct |
| 6 |
Correct |
25 ms |
23804 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
25 ms |
23800 KB |
Output is correct |
| 10 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 12 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 13 |
Incorrect |
25 ms |
23800 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
26 ms |
23908 KB |
Output is correct |
| 3 |
Correct |
30 ms |
23864 KB |
Output is correct |
| 4 |
Correct |
27 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
25 ms |
23800 KB |
Output is correct |
| 6 |
Correct |
25 ms |
23804 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
25 ms |
23800 KB |
Output is correct |
| 10 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 12 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 13 |
Incorrect |
25 ms |
23800 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
26 ms |
23908 KB |
Output is correct |
| 3 |
Correct |
30 ms |
23864 KB |
Output is correct |
| 4 |
Correct |
27 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
25 ms |
23800 KB |
Output is correct |
| 6 |
Correct |
25 ms |
23804 KB |
Output is correct |
| 7 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 9 |
Correct |
25 ms |
23800 KB |
Output is correct |
| 10 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 12 |
Correct |
26 ms |
23800 KB |
Output is correct |
| 13 |
Incorrect |
25 ms |
23800 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
