ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1111. Квадраты

got wa#3?? strange...
Послано Ivan 16 авг 2010 04:19
#include <stdio.h>
#include <math.h>
#define M_PI_4     0.785398163397448309616

double d[51] = {0};
char printed[51] = {0};

struct point {
double x;
double y;
};

struct square {
point a;
point b;
} squares[51];

point rotate(point a, double d_al){
point _a;
_a.x = a.x * cos(d_al) - a.y * sin(d_al);
_a.y = a.x * sin(d_al) + a.y * cos(d_al);
return _a;
}

double get_d(point a, point p) {
return sqrt((double)((a.x - p.x)*(a.x-p.x) + (a.y -p.y)*(a.y - p.y)));
}

int main () {
    int n;
    scanf("%d",&n);
    point p;
    int i;
    for (i=1;i<=n;i++) {
        scanf("%lf%lf%lf%lf", &squares[i].a.x,&squares[i].a.y,&squares[i].b.x,&squares[i].b.y);
    }
    scanf("%lf%lf", &p.x,&p.y);
    double tn;
    double alpha,d_al;
    point _a,_b,_p,a,b,temp;
    for(i=1;i<=n;i++) {
        b = squares[i].b;
        a = squares[i].a;
        if(a.x == b.x && a.y == b.y) {
            d[i] = get_d(p,a);
            continue;
        }
        tn = (double)(b.y - a.y)/(double)(b.x - a.x);
        alpha = atan(tn);
        d_al = M_PI_4 - alpha;
        _a = rotate(a,d_al);
        _b = rotate(b,d_al);
        _p = rotate(p,d_al);
        if( _a.x > _b.x) {
            temp = _b;
            _b = _a;
            _a = temp;
        }

        if(_p.y > _b.y) {
            if(_p.x < _a.x) {
                temp.x = _a.x;
                temp.y = _b.y;
                d[i] = get_d(_p,temp);
                continue;
            }
            if(_p.x > _b.x) {
                d[i] = get_d(_p,_b);
                continue;
            }
            d[i] = _p.y - _b.y;
            continue;
        }
        if(_p.y < _a.y) {
            if(_p.x > _b.x) {
                temp.x = _b.x;
                temp.y = _a.y;
                d[i] = get_d(_p,temp);
                continue;
            }
            if(_p.x < _a.x) {
                d[i] = get_d(_p,_a);
                continue;
            }
            d[i] = _a.y - _p.y;
            continue;
        }
        if(_p.x < _a.x) {
            d[i] = _a.x - _p.x;
            continue;
        }
        if(_p.x > _b.x) {
            d[i] = _p.x - _b.x;
            continue;
        }
        d[i] = 0;
    }

    double min;
    int j,k;
    for(i=1;i<=n;i++) {
        min = 99999999999999999;
        k = 0;
        for(j=1;j<=n;j++)
            if(!printed[j] && min > d[j]) {
                min = d[j];
                k = j;
            }
        printed[k] = 1;
        printf("%d ", k);
    }

return 0;}