acm.sgu.ru 192 помогите решить

[FiRi]

Условие: Дается N отрезков на плоскости (0<N<=300). Каждый отрезок определяется с помощью координат крайних точек (xi1,yi1) (xi2,yi2) (i=1,...,N). Все координаты находятся в диапазоне от нуля до 32000. Отрезки имеют не более одной общей точки. Каждый из отрезков окрашен в один из трех цветов: красный(R), зеленый(G), и синий (B). Отрезки проецируются на ось Ох. Проецируются на ось те прямые у которых координаты Y меньше (ближе к оси oX). Найти общую длину проекций окрашенных в красный, зеленый, и синий цвета.
Input:
Первая строка содержит число N. Каждая из следующих N строк содержит содержат координаты концов отрезков (4 целых числа разделяются в пространстве) и буква R, G, B в зависимости от цвета прямой.
Output:
Первая строка должна содержать букву R и длину проекции разделенных пробелом. Вторая строка должна содержать G и длину. Третья B и длину.
Input

4
1 1 3 2 R
2 1 4 2 G
3 1 5 2 B
2 2 3 5 R

Output

R 1
G 1
B 2

P.S. Во вложении лежит график построенный по тесту приведенному выше

[FiRi]

/*
* File: main.cpp
* Author: FiRi
*
* Created on 9 Июнь 2010 г., 13:55
*/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define eps 0.01


class Strenght
{
public:
double x1,x2,y1,y2,A,B,C;
int color;
int flag;
};

class oX
{
public:
int color;
double y;
};

int N;
double answer[3];
Strenght line[500];
oX X[3200000];

void replace(int &a, int &b)
{
int c=a;
a=b;
b=c;
}

void GetEquation(int i) // Получение A, B и С для уравнения прямой
{
line[i].A=line[i].y2-line[i].y1;
line[i].B=line[i].x1-line[i].x2;
line[i].C=line[i].y1*line[i].x2-line[i].y2*line[i].x1;

}

void reading() // считывание
{
scanf("%i",&N);
char colour[2];
int x1, x2, y1, y2;
for (int i=0;i<N;i++)
{
scanf("%i %i %i %i %s",&x1,&y1,&x2,&y2, &colour);
if (x1==x2)
{
i--;
N--;
continue;
}
if (x1>x2)
{
replace(x1,x2);
replace(y1,y2);
}
line[i].x1=x1;
line[i].x2=x2;
line[i].y1=y1;
line[i].y2=y2;
if(colour[0]=='R')
{
line[i].color=0;
}
if(colour[0]=='G')
{
line[i].color=1;
}
if(colour[0]=='B')
{
line[i].color=2;
}
GetEquation(i);
}
}

double MaxX(Strenght l)
{
if(l.x1>l.x2)
{
return l.x1;
}
return l.x2;
}

double MinX(Strenght l)
{
if (l.x1<l.x2)
{
return l.x1;
}
return l.x2;
}

double MaxY(Strenght l)
{
if (l.y1>l.y2)
{
return l.y1;
}
return l.y2;
}

double MinY(Strenght l)
{
if (l.y1<l.y2)
{
return l.y1;
}
return l.y2;
}

int is_preparation(int i, int j, double &x, double &y)// Проверка на
// пересечение
{
if(line[i].B*line[j].A==line[i].A*line[j].B)
{
return 0;
}
if(line[i].A==0)
{
y=-1*(line[i].C/line[i].B);
x=y*(-1)*(line[j].B/line[j].A)-line[j].C/line[j].A;
}
else
{
if(line[j].A==0)
{
y=-1*(line[j].C/line[j].B);
x=y*(-1)*(line[i].B/line[i].A)-line[i].C/line[i].A;
}
else
{
y=line[i].A*line[j].C-line[i].C*line[j].A;
y/=line[i].B*line[j].A-line[i].A*line[j].B;
x=-1*line[j].B/line[j].A*y-line[j].C/line[j].A;
}
}
if(x<=MinX(line[i])) return 0;
if(x>=MaxX(line[i])) return 0;
if(x<=MinX(line[j])) return 0;
if(x>=MaxX(line[j])) return 0;
if(y<=MinY(line[i])) return 0;
if(y>=MaxY(line[i])) return 0;
if(y<=MinY(line[j])) return 0;
if(y>=MaxY(line[j])) return 0;
return 1;
}


void preparation() //Разделение прямых при пересечении
{
double x,y;
for (int i=0;i<N;i++)
{
for (int j=i+1;j<N;j++)
{
if(is_preparation(i,j,x,y))
{
line[N]=line[i];
line[N].x1=x;
line[N].y1=y;
line[i].x2=x;
line[i].y2=y;
N++;
line[N]=line[j];
line[N].x1=x;
line[N].y1=y;
line[j].x2=x;
line[j].y2=y;
N++;
}
}
}
}

void search() // Поиск
{
;
}

void printing() // Вывод
{
printf("R %0.2lf\n",answer[0]);
printf("G %0.2lf\n",answer[1]);
printf("B %0.2lf\n",answer[2]);
}

int main(int argc, char** argv)
{
reading();
preparation();
search();
printing();
return (EXIT_SUCCESS);
}

[FiRi]

Не знаю, как сделать алгоритм проецирования, прочел и про z-буфер и про алгоритм художника, и все равно сделать не могу Помогите пожалуйста хотя-бы идеей

[MBo]

Ошибки перевода:
Дается N отрезков
на ось те отрезки, у которых координаты Y меньше (ближние к оси OX)

Вычисляются все точки пересечения, и вместе с концами отрезков заносятся в массив. Для каждой из точек записывается также, какой цвет идет правее -0, если конец отрезка, либо цвет отрезка, участвующего в пересечении, который образует наименьший угол с вектором -0Y, и уравнение этого отрезка. Сортируется по X. Далее идем слева направо по массиву. Если очередная точка не выше вертикальной проекции на текущий отрезок, меняем текущий цвет на её цвет.
Сложность квадратичная от N

[FiRi]

Перевод исправил. Как сделаю выложу код.

[FiRi]

Вычисляются все точки пересечения, и вместе с концами отрезков заносятся в массив. Для каждой из точек записывается также, какой цвет идет правее -0, если конец отрезка, либо цвет отрезка, участвующего в пересечении, который образует наименьший угол с вектором -0Y, и уравнение этого отрезка.N

Все вроде понятно, но вот насчет концов отрезка, концы которые правее для них как вычислять какой цвет начнется?

[MBo]

Не понял вопроса, переформулируй

[FiRi]

Ты написал, что надо записывать цвет для каждой точки. Так вот для точек пересечения понял, для левой точки конца отрезка тоже понятно, а вот для правой точки как цвет определить?

[MBo]

0,0-4,3 R
1,2-2,1 G
3,1-5,6 B
Точки, сорт. по X (пересечения примерно на глазок)
0,0 начался R
1,2 точка выше текущего, игнор
1.8, 1.2 начался G, добавляем к RSum разность 1.8-0
2,1 закончился G, добавляем разность, начался R
3,1 точка ниже, закончился R, начался B
3.5,2.5 закончился B, начался R
4,3 закончился R, начался B
5,6 закончился B

В точках 2,1 и 4,3 можно не искать сразу, какой отрезок станет текущим, а определять это в следующей точке.

[FiRi]

Благодарю, все понял