## 10927 - Bright Lights

**Moderator:** Board moderators

### 10927 - Bright Lights

Anyone could tell me how to solve this problem?

Data set 1:

All the lights are visible. // dot here

Data set 2:

Some lights are not visible: // colon here

x = -4, y = 4; // semicolon here

x = -2, y = 2. //dot here

- Pier
- New poster
**Posts:**38**Joined:**Thu Mar 27, 2003 9:12 pm**Location:**Aguascalientes, Mexico-
**Contact:**

I keep getting WA. I think it might be because of precision errors (I'm not very used to geometric problems). Any help appreciated.

Code: Select all

```
Const
error= 10e-7;
Type
punto= record
m: extended;
r,x,y,z: longint;
end;
Var
c,i,n,t: longint;
p: array [1..100000] of punto;
Function menor_m(a,b: punto): boolean;
begin
if (a.m + error< b.m) or
((abs(a.m -b.m)< error) and (a.z< b.z)) or
((abs(a.m -b.m)< error) and (a.z= b.z) and (sqr(a.x) + sqr(a.y) < sqr(b.x) + sqr(b.y)))
then menor_m:= true
else menor_m:= false;
end;
Function menor_x(a,b: punto): boolean;
begin
if (a.r < b.r) or
((a.r= b.r) and (a.x< b.x)) or
((a.r= b.r) and (a.x= b.x) and (a.y < b.y))
then menor_x:= true
else menor_x:= false;
end;
Procedure Qsort(l,r,m: longint);
var x,t: punto;
i,j: longint;
begin
i:= l; j:= r; x:= p[(l+r) shr 1];
repeat
if (m=0) then while menor_m(p[i], x) do Inc(i)
else while menor_x(p[i], x) do Inc(i);
if (m=0) then while menor_m(x, p[j]) do Dec(j)
else while menor_x(x, p[j]) do Dec(j);
if (i<=j) then
begin
t:= p[i]; p[i]:= p[j]; p[j]:= t;
Inc(i); Dec(j);
end;
until (i>j);
if (l<j) then Qsort(l,j,m);
if (i<r) then Qsort(i,r,m);
end;
Begin
c:= 0;
readln(input,n);
while (n<>0) do
begin
Inc(c);
for i:= 1 to n do
with (p[i]) do
begin
r:= 1;
readln(input,x,y,z);
if (x<>0) then m:= y/x
else m:= 1e100;
if (y=0) and (x<0) then m:= -0.1234567;
end;
Qsort(1,n,0);
t:= 0;
for i:= 1 to n-1 do
if (p[i].m= p[i+1].m) and (p[i].z= p[i+1].z) then
begin
Inc(t);
p[i+1].r:= 0;
end;
writeln(output,'Data set ',c,':');
if (t= 0) then writeln(output,'All the lights are visible.')
else begin
writeln(output,'Some lights are not visible:');
Qsort(1,n,1);
for i:= 1 to t-1 do
writeln(output,'x = ',p[i].x,', y = ',p[i].y,';');
writeln(output,'x = ',p[t].x,', y = ',p[t].y,'.');
end;
readln(input,n);
end;
End.
```

There are 10 kind of people on this world: those who understand binary and those who don't!

- Pier
- New poster
**Posts:**38**Joined:**Thu Mar 27, 2003 9:12 pm**Location:**Aguascalientes, Mexico-
**Contact:**

Here I define the precision.

Here I define a point, x,y,z are coordinates, m is the slope (using 0,0 as the other point) and r is used to indicate if it's visible (1= visible, 0= not visible).Const

error= 10e-7;

I declare variables, c is for counting the number of tests, i is for loops, n is the number of points, t is the total of not visible points and p is where I store the points.Type

punto= record

m: extended;

r,x,y,z: longint;

end;

This funtion sorts the points by slope, then by z and then by distance.Var

c,i,n,t: longint;

p: array [1..100000] of punto;

This funtion sorts the points by slope, then by z and then by distance.Function menor_m(a,b: punto): boolean;

begin

if (a.m + error< b.m) or

((abs(a.m -b.m)< error) and (a.z< b.z)) or

((abs(a.m -b.m)< error) and (a.z= b.z) and (sqr(a.x) + sqr(a.y) < sqr(b.x) + sqr(b.y)))

then menor_m:= true

else menor_m:= false;

end;

The sorting funtion.Function menor_x(a,b: punto): boolean;

begin

if (a.r < b.r) or

((a.r= b.r) and (a.x< b.x)) or

((a.r= b.r) and (a.x= b.x) and (a.y < b.y))

then menor_x:= true

else menor_x:= false;

end;

Procedure Qsort(l,r,m: longint);

var x,t: punto;

i,j: longint;

begin

i:= l; j:= r; x:= p[(l+r) shr 1];

repeat

if (m=0) then while menor_m(p, x) do Inc(i)

else while menor_x(p, x) do Inc(i);

if (m=0) then while menor_m(x, p[j]) do Dec(j)

else while menor_x(x, p[j]) do Dec(j);

if (i<=j) then

begin

t:= p; p:= p[j]; p[j]:= t;

Inc(i); Dec(j);

end;

until (i>j);

if (l<j) then Qsort(l,j,m);

if (i<r) then Qsort(i,r,m);

end;

The main part. Read number of points and while it's not zero process. I read all the points and find the slope. If x=0 then the slope is infinite (I used 1e100). As all the points have y>=0, if two points have the same slope and z then one is visible and the other is not. The only exception is when y=0, so I check whether x is positive or negative. If it's negative then I asign it a unique slope (which is -0.1234567). This is to avoid having to add additional checking for just one case.

Next I sort using the first function and then I check whether they are visible or not. If there all are visible (t=0) then I write it, else I sort using the second function and the print all light which are not visible.

The main part. Read number of points and while it's not zero process. I read all the points and find the slope. If x=0 then the slope is infinite (I used 1e100). As all the points have y>=0, if two points have the same slope and z then one is visible and the other is not. The only exception is when y=0, so I check whether x is positive or negative. If it's negative then I asign it a unique slope (which is -0.1234567). This is to avoid having to add additional checking for just one case.

Next I sort using the first function and then I check whether they are visible or not. If there all are visible (t=0) then I write it, else I sort using the second function and the print all light which are not visible.

Begin

c:= 0;

readln(input,n);

while (n<>0) do

begin

Inc(c);

for i:= 1 to n do

with (p) do

begin

r:= 1;

readln(input,x,y,z);

if (x<>0) then m:= y/x

else m:= 1e100;

if (y=0) and (x<0) then m:= -0.1234567;

end;

Qsort(1,n,0);

t:= 0;

for i:= 1 to n-1 do

if (p.m= p[i+1].m) and (p.z= p[i+1].z) then

begin

Inc(t);

p[i+1].r:= 0;

end;

writeln(output,'Data set ',c,':');

if (t= 0) then writeln(output,'All the lights are visible.')

else begin

writeln(output,'Some lights are not visible:');

Qsort(1,n,1);

for i:= 1 to t-1 do

writeln(output,'x = ',p.x,', y = ',p.y,';');

writeln(output,'x = ',p[t].x,', y = ',p[t].y,'.');

end;

readln(input,n);

end;

End.

*[/code]*There are 10 kind of people on this world: those who understand binary and those who don't!

- Christian Schuster
- Learning poster
**Posts:**63**Joined:**Thu Apr 04, 2002 2:00 am

### 10927 - Bright Lights

I don't know but i am getting WA! can any one help me?

for others. just be sure that you are not using any floating calculation. and at 0,0 there is no pole other than totem.

Code: Select all

`AC`

Last edited by shanto86 on Tue Jun 20, 2006 11:44 am, edited 1 time in total.

Self judging is the best judging!

- the LA-Z-BOy
- Learning poster
**Posts:**94**Joined:**Wed Jul 31, 2002 12:44 pm**Location:**Dacca, Bangladesh-
**Contact:**

**does**use floating point arithmetics (for polar coordinates). I didn't even use < EPSILON for equality checks, but ==. I was aware of the possibility of doing it integer-only, but I thought, let's try floats first, it's easier to code and I can still rewrite if it doesn't work.

In other words: It is okay to use FP for this problem. Just use it correctly.