http://acm.pku.edu.cn/JudgeOnline/problem?id=1070
Условие: Деформированное колесо
Код:
#include <cstdio> #include <algorithm> #include <vector> #include <cmath> using namespace std; const double EPS = 1e-6; const double MAX = 0x7fffffff; const double pi = acos(-1.0); int n; struct point { double x, y; point() { } point(double x, double y) { this->x = x; this->y = y; } point operator - (point a) { return point(x - a.x, y - a.y); } }; vector<point> vp; point g, last; struct seg { double length; double slope; point a, b; seg(double length, double slope) { this->length = length; this->slope = slope; } }; vector<seg> vs; int dblcmp(double d) { if(fabs(d) < EPS) return 0; return (d > 0) ? 1 : -1; } int dblcmp(double a, double b) { return dblcmp(a - b); } double fix(double d) { if(fabs(d) < 1e-3) return 0; return d; } double dot(point a, point b) { return a.x * b.x + a.y * b.y; } double cross(const point &a, const point &b) { return a.x * b.y - a.y * b.x; } int between(point c, point a, point b) { return dblcmp(dot(a - c, b - c)); } bool on_seg(point a, seg s) { return dblcmp(cross(s.b - s.a, a - s.a)) == 0 && (between(a, s.a, s.b) == 0 || between(a, s.a, s.b) == -1); } double sqr(double x) { return x * x; } double dist(const point &a, const point &b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); } bool on_hill(point p) { for(vector<seg>::iterator it = vs.begin(); it != vs.end(); ++ it) if(on_seg(p, *it)) { return true; } return false; } bool check(double angle, double x, double y) { point vc, nvc; vc.x = g.x - x; vc.y = g.y - y; nvc.x = vc.x * cos(angle) - vc.y * sin(angle); nvc.y = vc.x * sin(angle) + vc.y * cos(angle); int d1 = dblcmp(cross(point(0, 1), vc)); int d2 = dblcmp(cross(point(0, 1), nvc)); int d3 = dblcmp(cross(vc, nvc)); return dblcmp(nvc.y + y, g.y) == -1 && (d1 >= 0 && d2 >= 0 && d3 > 0 || d1 <=0 && d2 <= 0 && d3 < 0); } void update(double x, double y, double x1, double y1, double x2, double y2, double &left_angle, double &right_angle) { double angle; double D1, D2; point V1, V2; V1.x = x1 - x; V1.y = y1 - y; V2.x = x2 - x; V2.y = y2 - y; D1 = dist(point(x, y), point(x1 ,y1)); D2 = dist(point(x, y), point(x2, y2)); double v = dot(V1, V2) / (D1 * D2); if(v > 1) v = 1; else if(v < -1) v = -1; angle = acos(v); int d1 = dblcmp(x2, x); int d2 = dblcmp(cross(point(x1 - x, y1 - y), point(x2 - x, y2 - y))); if(d1 == -1) { if(d2 == -1) angle = 2 * pi - angle; if(dblcmp(angle, left_angle) == -1) left_angle = angle; } else if(d1 == 1) { if(d2 == 1) angle = 2 * pi - angle; if(dblcmp(angle, right_angle) == -1) right_angle = angle; } } int solve(double x, double y, double r, const seg &s, double x2[2], double y2[2]) { int ans_n = 0; double AB, BC, AC; AB = dist(point(x, y), s.a); AC = dist(point(x, y), s.b); BC = s.length; double a, b, c, delta; a = BC; b = -(sqr(AB) + sqr(BC) - sqr(AC)); c = BC * (sqr(AB) - sqr(r)); delta = sqr(b) - 4 * a * c; if(delta < 0) return 0; double m[2]; m[0] = (-b + sqrt(delta)) / (2 * a); m[1] = (-b - sqrt(delta)) / (2 * a); for(int i = 0; i < 2; ++ i) if(dblcmp(m[i], 0) >= 0 && dblcmp(m[i], BC) <= 0) { x2[ans_n] = (s.a.x * (BC - m[i]) + m[i] * s.b.x) / BC; y2[ans_n] = (s.a.y * (BC - m[i]) + m[i] * s.b.y) / BC; ans_n ++; } return ans_n; } bool rotate(int point_id) { double left_angle = MAX; double right_angle = MAX; double x, y, x1, y1, x2[2], y2[2]; double r; x = vp[point_id].x; y = vp[point_id].y; for(int i = 0; i < n; ++ i) if(i != point_id) { x1 = vp[i].x; y1 = vp[i].y; r = dist(vp[i], vp[point_id]); for(vector<seg>::iterator its = vs.begin(); its != vs.end(); ++ its) { int ans_n = solve(x, y, r, *its, x2, y2); for(int j = 0; j < ans_n; ++ j) update(x, y, x1, y1, x2[j], y2[j], left_angle, right_angle); } } double angle = MAX; if(dblcmp(left_angle, 0) != 0 && dblcmp(left_angle, MAX) != 0 && check(left_angle, vp[point_id].x, vp[point_id].y)) angle = left_angle; else if(dblcmp(right_angle, 0) != 0 && dblcmp(right_angle, MAX) != 0 && check(-right_angle, vp[point_id].x, vp[point_id].y)) angle = -right_angle; if(dblcmp(angle, MAX) == 0) return false; point vc, nvc; for(int i = 0; i < n; ++ i) if(i != point_id) { vc.x = vp[i].x - vp[point_id].x; vc.y = vp[i].y - vp[point_id].y; nvc.x = vc.x * cos(angle) - vc.y * sin(angle); nvc.y = vc.x * sin(angle) + vc.y * cos(angle); vp[i].x = nvc.x + vp[point_id].x; vp[i].y = nvc.y + vp[point_id].y; } vc.x = g.x - vp[point_id].x; vc.y = g.y - vp[point_id].y; nvc.x = vc.x * cos(angle) - vc.y * sin(angle); nvc.y = vc.x * sin(angle) + vc.y * cos(angle); g.x = nvc.x + vp[point_id].x; g.y = nvc.y + vp[point_id].y; return true; } bool rotate() { for(int i = 0; i < n; ++ i) if(on_hill(vp[i]) && rotate(i)) { return true; } return false; } int main() { int t; scanf("%d", &t); while(t --) { scanf("%d", &n); vp.clear(); for(int i = 0; i < n; ++ i) { double x, y; scanf("%lf %lf", &x, &y); vp.push_back(point(x, y)); } scanf("%lf %lf", &g.x, &g.y); vs.clear(); double l, s; do { scanf("%lf %lf", &l, &s); vs.push_back(seg(l, s)); } while(dblcmp(s)); scanf("%lf %lf", &last.x, &last.y); for(vector<seg>::iterator it = vs.begin(); it != vs.end(); ++ it) { it->b.x = last.x; it->b.y = last.y; it->a.x = last.x - it->length / sqrt(1 + sqr(it->slope)); it->a.y = last.y - it->length * it->slope / sqrt(1 + sqr(it->slope)); last.x = it->a.x; last.y = it->a.y; } while(rotate()); printf("%.3lf %.3lf\n", fix(g.x), fix(g.y)); } }