Submission #56658

#	Time	Username	Problem	Language	Result	Execution time	Memory
56658		ksun48	Fences (JOI18_fences)	C++14	100 / 100	404 ms	3436 KiB

fences

#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;
}
pair<double,int> dist[250][250][2];
void join(int a, int b, int w, double len){
	if(dist[a][b][0].second == w){
		dist[a][b][0].first = min(dist[a][b][0].first, len);
	} else if(dist[a][b][1].second == w){
		dist[a][b][1].first = min(dist[a][b][1].first, len);			
	} else if(len < dist[a][b][1].first){
		dist[a][b][1] = {len, w};
	}
	if(dist[a][b][0] > dist[a][b][1]){
		swap(dist[a][b][0], dist[a][b][1]);
	}
}
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);
	}

	double ans = 200000.0;
	for(int i = 0; i < pts.size(); i++){
		for(int j = 0; j < pts.size(); j++){
			dist[i][j][0] = {200000.0, 0};
			dist[i][j][1] = {200000.0, 1};
		}
	}

	for(int i = 0; i < edges.size(); i++){
		join(edges[i].first, edges[i].second, winds[i], length[i]);
	}
	for(int k = 0; k < pts.size(); k++){
		for(int i = 0; i < pts.size(); i++){
			for(int j = 0; j < pts.size(); j++){
				for(int q = 0; q < 4; q++){
					join(i, j, dist[i][k][q/2].second + dist[k][j][q%2].second, 
						dist[i][k][q/2].first + dist[k][j][q%2].first);
				}
			}
		}
	}
	for(int i = 0; i < pts.size(); i++){
		if(dist[i][i][0].second != 0){
			ans = min(ans, dist[i][i][0].first);
		}
		if(dist[i][i][1].second != 0){
			ans = min(ans, dist[i][i][1].first);
		}
	}
	printf("%.10lf\n", ans);
}

Compilation message (stderr)

fences.cpp: In function 'int main()':
fences.cpp:110:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < segs.size(); i++){
                 ~~^~~~~~~~~~~~~
fences.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++){
                 ~~^~~~~~~~~~~~
fences.cpp:119:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < pts.size(); j++){
                  ~~^~~~~~~~~~~~
fences.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++){
                 ~~^~~~~~~~~~~~
fences.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < segs.size(); j++){
                  ~~^~~~~~~~~~~~~
fences.cpp:147:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < segs.size(); i++){
                 ~~^~~~~~~~~~~~~
fences.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++){
                 ~~^~~~~~~~~~~~
fences.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < pts.size(); j++){
                  ~~^~~~~~~~~~~~
fences.cpp:165:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edges.size(); i++){
                 ~~^~~~~~~~~~~~~~
fences.cpp:168:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int k = 0; k < pts.size(); k++){
                 ~~^~~~~~~~~~~~
fences.cpp:169:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < pts.size(); i++){
                  ~~^~~~~~~~~~~~
fences.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < pts.size(); j++){
                   ~~^~~~~~~~~~~~
fences.cpp:178:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < pts.size(); i++){
                 ~~^~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49