Отримання знань

дистанційна підтримка освіти школярів


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

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на C++:

#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));
}
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)