Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.06.2010, 12:41
Новичок

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

acm.sgu.ru 192 помогите решить
Условие: Дается 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. Во вложении лежит график построенный по тесту приведенному выше
Изображения:
Тип файла: jpg Безимени-2.jpg (34.7 Кб, 42 просмотров)

Последний раз редактировалось FiRi, 13.06.2010 в 11:26.
  #2  
Старый 11.06.2010, 12:44
Новичок

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

/*
* 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, 11.06.2010 в 12:47.
  #3  
Старый 11.06.2010, 12:45
Новичок

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

Не знаю, как сделать алгоритм проецирования, прочел и про z-буфер и про алгоритм художника, и все равно сделать не могу Помогите пожалуйста хотя-бы идеей
  #4  
Старый 11.06.2010, 15:03
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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

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

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

Перевод исправил. Как сделаю выложу код.
  #6  
Старый 13.06.2010, 12:59
Новичок

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

Сообщение от MBo Посмотреть сообщение
Вычисляются все точки пересечения, и вместе с концами отрезков заносятся в массив. Для каждой из точек записывается также, какой цвет идет правее -0, если конец отрезка, либо цвет отрезка, участвующего в пересечении, который образует наименьший угол с вектором -0Y, и уравнение этого отрезка.N
Все вроде понятно, но вот насчет концов отрезка, концы которые правее для них как вычислять какой цвет начнется?
  #7  
Старый 13.06.2010, 13:28
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Не понял вопроса, переформулируй
  #8  
Старый 13.06.2010, 13:32
Новичок

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

Ты написал, что надо записывать цвет для каждой точки. Так вот для точек пересечения понял, для левой точки конца отрезка тоже понятно, а вот для правой точки как цвет определить?
  #9  
Старый 13.06.2010, 14:08
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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 можно не искать сразу, какой отрезок станет текущим, а определять это в следующей точке.
  #10  
Старый 13.06.2010, 14:22
Новичок

Отправить личное сообщение для FiRi Посмотреть профиль Найти все сообщения от FiRi
 
Регистрация: 11.06.2010
Сообщений: 7

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите решить задачу. Loonar Графы 10 12.12.2010 15:42
Помогите решить 2 задачи на C++ BanG Реализация, исходники, языки 1 30.12.2009 21:45
Помогите решить задачу на С++ Andrei Реализация, исходники, языки 1 21.12.2008 16:14
помогите решить!!! гость Математические алгоритмы 0 06.08.2008 14:00
Помогите решить. гость Математические алгоритмы (другое) 3 19.11.2007 10:43