Submission #56647

#TimeUsernameProblemLanguageResultExecution timeMemory
56647ksun48Fences (JOI18_fences)C++14
0 / 100
3 ms504 KiB
#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; return r; } 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; 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 = 15; 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 < pts.size(); 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 (stderr)

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:168:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pts.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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...