一直RE求调/kel
  • 板块UVA10263 Railway
  • 楼主Tony2
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/5/20 17:34
  • 上次更新2023/11/4 23:02:08
查看原帖
一直RE求调/kel
171288
Tony2楼主2021/5/20 17:34
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
namespace Geo{
	typedef double ld;
	const ld eps = 1e-8, pi = atan2(0, -1);
	bool check0(ld x){
		return fabs(x) < eps;
	}
	struct point{
		ld x, y;
		point(ld x=0, ld y=0): x(x), y(y) {}
		point operator = (const point &b){
			x = b.x, y = b.y;
		}
		bool operator == (const point &b) const{
			return check0(x-b.x)&&check0(y-b.y);
		}
		bool operator != (const point &b) const{
			return !(*this==b);
		}
		point operator + (const point &b) const{
			return point(x+b.x, y+b.y);
		}
		point operator - (const point &b) const{
			return point(x-b.x, y-b.y);
		}
		ld operator | (const point &b) const{
			return x*b.x+y*b.y;
		}
		ld operator * (const point &b) const{
			return x*b.y-b.x*y;
		}
		point operator * (const ld &b) const{
			return point(x*b, y*b);
		}
		point operator / (const ld &b) const{
			if (check0(b)){
				cout << "aaaaa";
				exit(0);
			}
			return point(x/b, y/b);
		}
		ld getd() const{
			return atan2(y, x);
		}
		ld norm() const{
			return x*x+y*y;
		}
		ld abs() const{
			return sqrt(norm());
		}
		bool operator < (const point &b) const{return getd()<b.getd();}
	};
	ld check3(point a, point b, point c){
		return (b-a)*(c-b);
	}
	bool left(point a, point b, point c){
		return check3(a, b, c) > eps;
	}
	bool right(point a, point b, point c){
		return check3(a, b, c) < eps;
	}
	bool oneline(point a, point b, point c){
		return fabs(check3(a, b, c)) < eps;
	}
	bool inbox(point a, point b, point p){
		ld minx = min(a.x, b.x), maxx = max(a.x, b.x);
		ld miny = min(a.y, b.y), maxy = max(a.y, b.y);
		return minx <= p.x && p.x <= maxx && miny <= p.y && p.y <= maxy;
	}
	struct segment;
	struct line{
		point a, v;
		line(point a=point(), point v=point()): a(a), v(v) {}
		line(segment s);
		point operator & (const line &l) const{
			ld m = (a.x*v.y-a.y*v.x-l.a.x*v.y+l.a.y*v.x)
				  /(l.v.x*v.y-v.x*l.v.y);
			return l.a+l.v*m;
		}
		bool operator | (const point &b) const{
			return check0((b.x-a.x)*v.y-(b.y-a.y)*v.x);
		}
	};
	point project(point p, line l){
		if (check0(l.v.norm())){
			cout << "fuck";
			exit(0);
		}
		return l.a+l.v*(((p-l.a)|l.v)/l.v.norm());
	}
	struct segment{
		point a, b;
		segment(point a=point(), point b=point()): a(a), b(b) {}
		point operator & (const segment &s) const{
			return line(*this)&line(s);
		}
		bool inbox(point p){
			return Geo::inbox(a, b, p);
		}
	};
	line::line(segment s): a(s.a), v(s.b-s.a) {}
	point project(point p, segment s){
		return project(p, line(s));
	}
	point nearest(point p, segment s){
		if (s.a == s.b) return s.a;
		point res = project(p, s);
		if (!s.inbox(res)) return (p-s.a).norm()<(p-s.b).norm()?s.a:s.b;
		else return res;
	}
	struct polygon{
		vector<point> vec;
		polygon(){vec.clear();}
		void push_back(point p){
			vec.push_back(p);
		} 
		bool operator | (const point &p) const{
			bool ok = 1;
			for (int i = 0; i < ((int)vec.size())-1; i++)
				if (check3(vec[i], vec[i+1], p) <= eps)
					ok = 0;
			if (check3(vec[((int)vec.size())-1], vec[0], p) <= eps)
				ok = 0;
			return ok;
		}
		bool operator | (const segment &s) const{
			return ((*this)|s.a) && ((*this)|s.b);
		}
	};
	bool checkintersection(segment s1, segment s2){
		ld cp1 = check3(s1.a, s1.b, s2.a),
		   cp2 = check3(s1.a, s1.b, s2.b),
		   cp3 = check3(s2.a, s2.b, s1.a),
		   cp4 = check3(s2.a, s2.b, s1.b);
		if ((cp1*cp2) < 0 && (cp3*cp4) < 0)
			return true;
		if (check0(cp1) && s1.inbox(s2.a)) return true;
		if (check0(cp2) && s1.inbox(s2.b)) return true;
		if (check0(cp3) && s2.inbox(s1.a)) return true;
		if (check0(cp4) && s2.inbox(s1.b)) return true;
		return false;
	}
}
using namespace Geo;
int n;
ld mn;
point p, a, b, ans;
int main(){
	std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	while (cin >> p.x >> p.y >> n){
		cin >> a.x >> a.y;
		ans = a, mn = (p-a).norm();
		for (int i = 1; i <= n; i++){
			cin >> b.x >> b.y;
			segment s(a, b);
			point x = nearest(p, s);
			ld tmp = (p-x).norm();
			if (tmp < mn){
				mn = tmp;
				ans = x;
			}
			a = b;
		}
		cout << fixed << setprecision(4) << ans.x << endl << ans.y << endl;
	}
	return 0;
}

还有就是程序跑的有点慢……

2021/5/20 17:34
加载中...