| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56602 |
2018-07-12T02:52:52 Z |
ksun48 |
Fences (JOI18_fences) |
C++14 |
|
4 ms |
516 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double T;
const double PI = 3.1415926535;
const double EPS = 0.0000001;
struct P {
T x, y;
P() : x(0), y(0){}
P(T x, T y) : x(x), y(y) {}
P operator +(P p){
return P(x+p.x,y+p.y);
}
P operator -(P p){
return P(x-p.x,y-p.y);
}
P operator *(T t){
return P(x*t, y*t);
}
P operator /(T t){
return P(x,y) * (1.0/t);
}
T dist(){
return sqrt(x*x+y*y);
}
T angle(){
return atan2(y,x);
}
P rotate(T angle){
double c = cos(angle);
double s = sin(angle);
return P(c*x-s*y,s*x+c*y);
}
};
double get(){
double r;
cin >> r;
r += (double)((rand() % 2000) - 1000) / 20000000.0;
}
double ang;
int wind(P a1, P b1){
// 0, 1, -1 if it crosses y = tan(ang) * x
P a = a1.rotate(-ang);
P b = b1.rotate(-ang);
if((a-b).dist() < EPS) return 0;
if(a.y > 0 && b.y > 0) return 0;
if(a.y < 0 && b.y < 0) return 0;
double nx = a.x + (0.0 - a.y) / (b.y - a.y) * (b.x - a.x);
if(nx < 0) return 0;
if(a.y < b.y) return 1;
assert(wind(b1,a1) == 1);
return -1;
}
double S;
int bad(P a, P b){
// check if this intersects
// [-S, S] cross S
a.y -= S;
b.y -= S;
if((a-b).dist() < EPS) return 0;
if(a.y > 0 && b.y > 0) return 0;
if(a.y < 0 && b.y < 0) return 0;
double nx = a.x + (0.0 - a.y) / (b.y - a.y) * (b.x - a.x);
return (nx >= -S) && (nx <= S);
}
int ok(P a, P b){
if(bad(a.rotate(0),b.rotate(0))) return 0;
if(bad(a.rotate(PI/2.0), b.rotate(PI/2.0))) return 0;
if(bad(a.rotate(2.0*PI/2.0), b.rotate(2.0*PI/2.0))) return 0;
if(bad(a.rotate(3.0*PI/2.0), b.rotate(3.0*PI/2.0))) return 0;
return 1;
}
double dot(P a, P b){
return a.x*b.x + a.y*b.y;
}
int main(){
ang = 0.001;
int n;
cin >> n >> S;
vector<pair<P,P> > segs;
vector<pair<int,int> > idx;
for(int i = 0; i < n; i++){
P a, b;
a.x = get(); a.y = get(); b.x = get(); b.y = get();
segs.push_back({a,b});
}
segs.push_back({P(S,S),P(S,S)});
segs.push_back({P(S,-S),P(S,-S)});
segs.push_back({P(-S,S),P(-S,S)});
segs.push_back({P(-S,-S),P(-S,-S)});
S -= 0.0001;
// get from each point to each other point with nonzero winding number.
// winding number adds one when
P origin = P(0,0);
vector<P> pts;
for(int i = 0; i < segs.size(); i++){
idx.push_back({pts.size(), pts.size()+1});
pts.push_back(segs[i].first);
pts.push_back(segs[i].second);
}
vector<pair<int,int> > edges;
vector<int> winds;
vector<double> length;
for(int i = 0; i < pts.size(); i++){
for(int j = 0; j < pts.size(); j++){
if( !ok(pts[i], pts[j]) ) continue;
edges.push_back({i,j});
winds.push_back( wind(pts[i],pts[j]) );
length.push_back((pts[i]-pts[j]).dist());
}
}
for(int i = 0; i < pts.size(); i++){
for(int j = 0; j < segs.size(); j++){
P p1 = segs[j].first - pts[i];
P p2 = segs[j].second - pts[i];
if((p1-p2).dist() < EPS) continue;
double len = dot(p2-p1, origin-p1) / (p2-p1).dist();
P r = p1 + (p2 - p1) * (len) / (p2-p1).dist();
if((p1-r).dist() + (p2-r).dist() > (p1-p2).dist() + EPS){
continue;
}
if( !ok(pts[i], pts[i] + r) ) continue;
double cost = r.dist();
edges.push_back({i,idx[j].first});
winds.push_back( wind(pts[i], pts[i] + r) + wind(pts[i] + r, pts[idx[j].first]) );
length.push_back(cost);
edges.push_back({idx[j].first, i});
winds.push_back( -winds[winds.size()-1] );
length.push_back(cost);
}
}
for(int i = 0; i < segs.size(); i++){
assert(ok(segs[i].first, segs[i].second));
edges.push_back({idx[i].first, idx[i].second});
winds.push_back(wind(segs[i].first, segs[i].second));
length.push_back(0.0);
edges.push_back({idx[i].second, idx[i].first});
winds.push_back(wind(segs[i].second, segs[i].first));
length.push_back(0.0);
}
/*for(int i = 0; i < pts.size(); i++){
cout << i << " " << pts[i].x << " " << pts[i].y << '\n';
}
cout << '\n';
for(int i = 0; i < edges.size(); i++){
cout << edges[i].first << " " << edges[i].second << " " << winds[i] << " " << length[i] << '\n';
}*/
int maxw = n + 4;
int N = pts.size() * maxw;
double dist[N][N];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
dist[i][j] = 20000.0;
}
dist[i][i] = 0;
}
for(int i = 0; i < edges.size(); i++){
for(int r = 0; r < maxw; r++){
int w = winds[i];
if(w + r < 0 || w + r >= maxw) continue;
double &v = dist[edges[i].first * maxw + r][edges[i].second * maxw + w + r];
v = min(v, length[i]);
}
}
for(int k = 0; k < N; k++){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
double ans = 20000.0;
for(int i = 0; i < pts.size(); i++){
ans = min(ans, dist[i * maxw + 0][i * maxw + 1]);
}
printf("%.10lf\n", ans);
}
Compilation message
fences.cpp: In function 'double get()':
fences.cpp:40:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
fences.cpp: In function 'int main()':
fences.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < segs.size(); i++){
~~^~~~~~~~~~~~~
fences.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pts.size(); i++){
~~^~~~~~~~~~~~
fences.cpp:106:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < pts.size(); j++){
~~^~~~~~~~~~~~
fences.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pts.size(); i++){
~~^~~~~~~~~~~~
fences.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < segs.size(); j++){
~~^~~~~~~~~~~~~
fences.cpp:134:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < segs.size(); i++){
~~^~~~~~~~~~~~~
fences.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < edges.size(); i++){
~~^~~~~~~~~~~~~~
fences.cpp:175:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < pts.size(); i++){
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
516 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
516 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
3 ms |
484 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
516 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
