INFOMAN брой 21
/*
6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
Решение на задача LIGHT от второто контролно, Ямбол, 3 юни 2001 г.
------------------------------------------------------------------
Условие: Имаме светлинен точков източник с целочислени координати
(Bx, By) и N (< 500) на брой тръби представени като окръжности,
като i-тата окръжност има за център точка с цели координати (Cix, Ciy)
и радуис цяло число Ri. Тръбите не могат да се припокриват, не отразяват
светлина и не пропускат светлина през себе си.
Напишете програма LIGHT.EXE, която определя незастъпващите се части по
абцисата, които са в сянката на тръбите.
Вход: На първия ред - N - брой на тръбите,
на втория - Bx и By,
N реда с по три цели числа - Cix, Ciy, Ri,
като Ciy + Ri < By.
Всички числа са естествени и по-малки от 10 000.
Изход: Координатите на неосветените части, на отделни редове,
с точност две цифри след десетичната точка.
Интервалите да бъдат подредени по нарастваща X-координата.
Решение: 1) Ще намерим за всяка окръжност интервалът от абцисата,
ограничен от двете допирателни към окръжността от точковия
източник.
2) Ще обединим тези интервали. Забележете, че ако два
интервала са на разстояние по-малко от 0.01, то те практически
са долепени един до друг и следва да ги обединим в един.
1) Нека т. B (bx, by) е точковия светлинен източник, т. C (cx, cy) е
центъра една от N-те окръжности и r - съотв. радуис.
Нека допирателната от т. B към окръжността я допира в т. T (tx, ty).
Нека á = ъгъл TBC, à = ъгъл( BC, правата y = By ).
Тогава:
tx = bx - BT*cos(à - á), ty = by - BT*sin(à - á),
когато CTB е ляво ориентиран и
tx = bx - BT*cos(à + á), ty = by - BT*sin(à + á),
когато CTB е дясно ориентиран.
Ето и как се изчисляват съотв. синуси и косинуси:
cos(à - á) = cos(à)*cos(á) + sin(à)*sin(á);
cos(à + á) = cos(à)*cos(á) - sin(à)*sin(á);
sin(à - á) = sin(à)*cos(á) - cos(à)*sin(á);
sin(à + á) = sin(à)*cos(á) + cos(à)*sin(á);
cos(à) = (Bx - Cx) / BC; cos(á) = BT / BC;
sin(à) = (By - Cy) / BC; sin(á) = r / BC;
Записано в по-опростен вид се получава:
Tx = Bx - (BT / BC2)*( (Bx - Cx)*BT + (By - Cy)*r );
Ty = By - (BT / BC2)*( (By - Cy)*BT - (Bx - Cx)*r );
за едната допирна точка и
Tx = Bx - (BT / BC2)*( (Bx - Cx)*BT - (By - Cy)*r );
Ty = By - (BT / BC2)*( (By - Cy)*BT + (Bx - Cx)*r );
за другата.
Дотук имаме по две точки допирателните към окръжността - т. B и
съотв. т. Т. Остава да намерим къде правата BT пресича оста Ox.
Като заместим в уравнението на правата BT (y = a*x + b) y с 0,
получаваме:
x = Bx - By*(Bx - Tx) / (By - Ty);
2) Вече имаме редичка от интервали, които трябва да обединим.
2.1) Първо сортираме интервалите по нарастваща X-координата.
2.2) Правим си списък от краища на интервали (два типа - начало и край),
които също сортираме по X, и в случай, че имаме два края на една и съща
позиция, то слагаме началния преди крайния.
2.3) Обхождаме последователно краищата и при срещане на начало увеличаваме
с 1 брояча на текущо натрупаните един върху друг интервали, а при срещане
на край намаляваме този брояч. В момента, в който при срещане на начало
броячът стане 1, това означава, че започваме същински нов интервал и
след това при срещане на край и брояч = 0 => край на интервала.
Това е.
Забележка: Във връзка с формата на списанието, вход/изходът на програмата
е променен (закоментарен) от LIGHT.IN / LIGHT.OUT, на LIGHT.C / екран.
Мартин Вълканов
E-mail: mvalkanov@yahoo.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_N 500
typedef struct { long int x, y; } CPnt;
typedef struct { CPnt c; long int r; } CCircle;
typedef struct { double x, y; } CPntDouble;
typedef struct { double b, e; } CInterval;
typedef struct { double x; char cKind; int nInterval; } CEnd;
int n;
CPnt b;
int nIntervalCnt;
CInterval vIntervals[MAX_N];
int nFinalIntervalCnt;
CInterval vFinalIntervals[MAX_N];
int nEndCnt;
CEnd vEnds[MAX_N*2];
void pAddCircle( CCircle * c )
{
CPntDouble t1, t2;
double k1, k2;
long int BC2; double BT;
BC2 = (b.x - c->c.x) * (b.x - c->c.x) + (b.y - c->c.y) * (b.y - c->c.y);
BT = sqrt( BC2 - c->r * c->r );
t1.x = b.x - (BT / BC2)*( (b.x - c->c.x)*BT + (b.y - c->c.y)*c->r );
t1.y = b.y - (BT / BC2)*( (b.y - c->c.y)*BT - (b.x - c->c.x)*c->r );
t2.x = b.x - (BT / BC2)*( (b.x - c->c.x)*BT - (b.y - c->c.y)*c->r );
t2.y = b.y - (BT / BC2)*( (b.y - c->c.y)*BT + (b.x - c->c.x)*c->r );
k1 = b.x - b.y*(b.x - t1.x) / (b.y - t1.y);
k2 = b.x - b.y*(b.x - t2.x) / (b.y - t2.y);
vIntervals[ nIntervalCnt ].b = k1; vIntervals[ nIntervalCnt++ ].e = k2;
}
int fIntervalCmp( const void * a, const void * b )
{
CInterval * A = (CInterval *) a, * B = (CInterval *) b;
return ( A->b < B->b ) ? -1 : ( A->b > B->b ) ? 1 :
( A->e < B->e ) ? -1 : ( A->e > B->e );
}
int fEndCmp( const void * a, const void * b )
{
CEnd * A = (CEnd *) a, * B = (CEnd *) b;
return ( A->x < B->x ) ? -1 : ( A->x > B->x ) ? 1 :
( A->cKind < B->cKind ) ? -1 : ( A->cKind > B->cKind );
}
void pUniteIntervals( void )
{
int nStackSize = 0, i;
for ( i = 0; i < nEndCnt; i++ )
{
if ( vEnds[i].cKind == 'b' )
{
if ( ++nStackSize == 1 )
if ( nFinalIntervalCnt &&
( vEnds[i].x - vFinalIntervals[ nFinalIntervalCnt - 1 ].e <= 0.01 ) )
nFinalIntervalCnt--;
else
vFinalIntervals[ nFinalIntervalCnt ].b = vEnds[i].x;
}
else
if ( --nStackSize == 0 )
vFinalIntervals[ nFinalIntervalCnt++ ].e = vEnds[i].x;
}
}
int main( void )
{
int i;
char sTemp[200];
FILE * f = fopen( "light.c", "r" ); fgets( sTemp, 200, f );
// FILE * f = fopen( "light.in", "r" );
fscanf( f, "%d", &n ); fscanf( f, "%ld %ld", &b.x, &b.y );
for ( i = 0; i < n; i++ )
{
CCircle c;
fscanf( f, "%ld %ld %ld", &c.c.x, &c.c.y, &c.r );
pAddCircle( &c );
}
fclose(f);
qsort( vIntervals, nIntervalCnt, sizeof(CInterval), fIntervalCmp );
for ( i = 0; i < nIntervalCnt; i++ )
{
vEnds[ nEndCnt ].x = vIntervals[i].b;
vEnds[ nEndCnt ].cKind = 'b';
vEnds[ nEndCnt++ ].nInterval = i;
vEnds[ nEndCnt ].x = vIntervals[i].e;
vEnds[ nEndCnt ].cKind = 'e';
vEnds[ nEndCnt++ ].nInterval = i;
}
qsort( vEnds, nEndCnt, sizeof(CEnd), fEndCmp );
pUniteIntervals();
f = stdout;
// f = fopen( "light.out", "w" );
if ( nFinalIntervalCnt )
{
fprintf( f, "%.2lf %.2lf", vFinalIntervals[0].b, vFinalIntervals[0].e );
for ( i = 1; i < nFinalIntervalCnt; i++ )
fprintf( f, "\n%.2lf %.2lf", vFinalIntervals[i].b, vFinalIntervals[i].e );
}
fclose(f);
return 0;
}