Решение задачи "Прямая и квадраты" с Меньшиков

Без пояснения   Просмотров: 21


В прямоугольной декартовой системе координат прямая задана двумя принадлежащими ей точками (0, W) и (100N, E). Также заданы N2 квадратов со сторонами, параллельными осям координат. Квадрат Si, j имеет координаты углов (100i , 100j ) и (100i - 100, 100j - 100), i , j = 1, 2, ..., N. Требуется найти количество квадратов, имеющих общую точку с прямой.

Код

#include <iostream>
#include <cstdio>
 
using namespace std;
 
struct point
{
    int x,y;
    point(){}
    point(int X, int Y)
    {
        x = X;
        y = Y;
    }
};
struct line
{
    double a,b,c;
    line(){}
    line(point f, point s)
    {
        a = s.y - f.y;
        b = f.x - s.x;
        c = -a * f.x -b * f.y;
    }
    double getY(double x)
    {
        return (-a*x - c) / b;
    }
};
int N, W, E;
void input()
{
    cin>>N>>W>>E;
}
const double eps = 1e-8;
double fabs(double a)
{
    if (a<0)
        return -a;
    return a;
}
bool Equal(double a, double b)
{
    return fabs(a-b) <= eps;
}
bool Less(double a, double b)
{
    return (a < b && !Equal(a,b));
}
bool More(double a, double b)
{
    return (a > b && !Equal(a,b));
}
// a - положительное, поэтому корректировать +eps
bool isRoundDoulbe(double &a)
{
    //return a == (int)a; // может быть потеря точности double
    return fabs(a - (int)(a + eps)) <= eps;
}
// curY - находится на краю области и не является углом
// curY - нормированная величина (Y/100)
bool isSideNoCornerY(int curY)
{
    return curY !=0 && curY != N;
}
void solve()
{
    line l(point(0,W),point(100*N, E));
    // горизонтальная линия
    if (l.a == 0)
    {
        if (W%100 == 0 && W!=0 && W != 100*N)
            cout<<2*N;
        else
            cout<<N;
        return;
    }
   
    int crossRect = 0;
    int y = W;
    double prevY = l.getY(0) / 100;
 
    // начальная точка пересекает два прямогоульника
    // один из них считаем сразу(верхний или нижний)
    // второй во время первой итерации цикла
    if (isRoundDoulbe(prevY) && isSideNoCornerY(prevY))
        crossRect++;
 
    for (int x=1; x<=N;x++)
    {
        double curY = l.getY(100*x) / 100;
        if (isRoundDoulbe(curY))
        {
            if (x != N) // крестовина
                crossRect += 2;// диагональные квадраты
            else if (isSideNoCornerY(curY)) // квадрат снизу или сверху
                crossRect++;
        }
        if ((int)(curY + eps) != (int)(prevY + eps))
        {
            // убывающая линия
            if (More(prevY,curY)&& !isRoundDoulbe(prevY))
                crossRect++; // нижний квадрат
            // возрастающая линия
            if (Less(prevY,curY) && !isRoundDoulbe(curY))
                crossRect++; // верхний квадрат
        }
        crossRect++; // текущий квадрат
        prevY = curY;
    }
    cout<<crossRect;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться