http://acm.pku.edu.cn/JudgeOnline/problem?id=1070
Условие: Деформированное колесо

http://acm.pku.edu.cn/JudgeOnline/images/1070/c1.gif

Код:
#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));
    }
}