10927 - Bright Lights

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

10927 - Bright Lights

Post by zhang » Sun Oct 09, 2005 5:27 pm

Anyone could tell me how to solve this problem?

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sun Oct 09, 2005 6:17 pm

Just sort the points according to their angle from the origin, and then a linear search suffices to find the visible points (after which you need to sort them again to meet the output specifications). In fact, for the first sorting the only thing needed is that points collinear with (0, 0) are next to one another, and in increasing order of distance from the origin.

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

Post by zhang » Mon Oct 10, 2005 2:41 am

Thank u,I understand how to solve it.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

Post by wook » Mon Oct 17, 2005 11:40 am

10927 - Bright Lights

hi, I solved this problem with o(nlgn) algorithm.
I think my algorithm is not wrong, but i got WA several times.

can anyone give me some tricky test cases?
Thanks :)
Sorry For My Poor English.. :)

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Sun Oct 23, 2005 10:53 am

Hello, wook! Is your algorithm similar to david's? If it is, then yours should be correct too. You must be very precise, because there should be different punctuation marks in the output:

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

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

Post by Pier » Sun Oct 23, 2005 7:51 pm

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!

User avatar
N|N0
New poster
Posts: 36
Joined: Tue Jan 25, 2005 10:33 pm
Location: Ljubljana, Slovenija
Contact:

Post by N|N0 » Mon Oct 24, 2005 3:14 pm

Pier wrote:I keep getting WA. I think it might be because of precision errors (I'm not very used to geometric problems). Any help appreciated.
I think precision is not the case here. Why didn't you put comments to your code, explaining your idea? :-?

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

Post by Pier » Tue Oct 25, 2005 3:45 am

Here I define the precision.
Const
error= 10e-7;
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).
Type
punto= record
m: extended;
r,x,y,z: longint;
end;
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.
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;
This funtion sorts the points by slope, then by z and then by distance.
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;
The sorting funtion.
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.

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!

mysword
New poster
Posts: 26
Joined: Sun Mar 06, 2005 8:52 am

Post by mysword » Fri Nov 18, 2005 2:59 pm

The trick is that, the precision should be at least 1e-10, else will be got WA
good luck to all.

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

Post by Christian Schuster » Fri Dec 02, 2005 5:26 pm

@Pier:

Your test if a pole is visible is wrong. A pole occludes all poles having the same angle, a greater distance and at most the same size.

HTH,
Christian

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

10927 - Bright Lights

Post by shanto86 » Sat Jun 17, 2006 5:53 am

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

Code: Select all

AC
for others. just be sure that you are not using any floating calculation. and at 0,0 there is no pole other than totem.
Last edited by shanto86 on Tue Jun 20, 2006 11:44 am, edited 1 time in total.
Self judging is the best judging!

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

Post by the LA-Z-BOy » Sun Jun 18, 2006 3:10 pm

Most probably you are facing precision errors due to floating point calculation. It can be solved without using floating point arithmetic at all, only integers.
Istiaque Ahmed [the LA-Z-BOy]

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Jun 18, 2006 9:37 pm

yeh i also think so. i used here cosine. but i think i should use cot. it will make integer calculation possible let me try tomorrow and thanks for reply!
Self judging is the best judging!

SP8472
New poster
Posts: 9
Joined: Tue Nov 29, 2005 5:27 pm
Location: Karlsruhe, Germany

Post by SP8472 » Mon Jul 17, 2006 7:39 pm

I got AC on first try with a solution that 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.

SP8472
New poster
Posts: 9
Joined: Tue Nov 29, 2005 5:27 pm
Location: Karlsruhe, Germany

Post by SP8472 » Mon Jul 17, 2006 8:29 pm

Just for giggles, I just replaced all FP routines in a copy of my program with equivalent integer calculations.

The program was still accepted. It runs slightly slower, but not significantly so (about 10ms difference). The runtime is obviously dominated by all the sorting going on.

Post Reply

Return to “Volume 109 (10900-10999)”