10078 - The Art Gallery

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

Moderator: Board moderators

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

10078 - The Art Gallery

Post by likhan » Fri Sep 27, 2002 4:53 pm

For this problem I took consecutive three points and calculated whether all the tree paired points make a left turn or right turn.
Last edited by likhan on Fri Sep 27, 2002 5:39 pm, edited 1 time in total.

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Fri Sep 27, 2002 5:10 pm

You miss the last turn,

try:

Code: Select all

5
1 1
0 0
2 1
2 2
0 2
0
Kristoffer Hansen

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan » Fri Sep 27, 2002 5:37 pm

Thanx I have already sorted it out. And thanx again for spending your precious time to look over my code.

infinity
New poster
Posts: 1
Joined: Thu Mar 20, 2003 8:13 pm

10078

Post by infinity » Thu Mar 20, 2003 8:15 pm

#include <iostream>
using namespace std;

class Point
{
public:
Point( int, int );
int GetX() { return x; }
int GetY() { return y; }
private:
int x;
int y;
};

Point::Point( int GetX, int GetY )
{
x = GetX;
y = GetY;
}

class Line
{
public:
Line( Point *, Point * );
int ifSameSite( Point *, Point * );
private:
int x;
int y;
float Slope;
int Vertical;
};

Line::Line( Point *p1, Point *p2 )
{
x = p2->GetX();
y = p2->GetY();
if( p1->GetX()!=p2->GetX() )
{
Slope = (float)( p1->GetY() - p2->GetY() )/(float)( p1->GetX() - p2->GetX() );
Vertical = 0;
}
else
Vertical = 1;
}

int Line::ifSameSite( Point *p1, Point *p2 )
{
float v1=0, v2=0;

if( !Vertical )
{
v1 = Slope*( p1->GetX() - x )+( y - p1->GetY() );
v2 = Slope*( p2->GetX() - x )+( y - p2->GetY() );
}
else
{
v1 = p1->GetX() - x;
v2 = p2->GetX() - x;
}

if( v1*v2 < 0 )
return 1;
else
return 0;
}

void Find( int GetPoint )
{
Point **GetP;
int Found=0;
int i, x, y;

if( GetPoint > 3 )
{
GetP = new Point *[GetPoint];
for( i=0; i<GetPoint; i++ )
{
cin >>x>>y;
GetP = new Point( x, y );
}

for( i=0; i<GetPoint-1 && Found==0; i++ )
{
Line *CalLine = new Line( GetP[(i+1)%GetPoint], GetP[(i+2)%GetPoint] );
if( CalLine->ifSameSite( GetP[i%GetPoint], GetP[(i+3)%GetPoint] ) )
Found=1;
delete CalLine;
}
}

if( Found )
cout <<"Yes\n";
else
cout <<"No\n";
}

int main()
{
int GetPoint=0;

while( cin >>GetPoint && GetPoint!=0 )
Find( GetPoint );

return 0;
}


I always got a WA....
Please help me....

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Wed Mar 26, 2003 7:19 am

Convex Hull Algorithm :lol:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10078 The Art Gallery

Post by little joey » Fri Sep 05, 2003 6:29 pm

After avoiding the problem of convex hull finding for a long time, I finaly decided to dig into it and started trying my luck on it. With not much succes...
Problem 681 was dramatic and I still can't see why my program is wrong. So I tried my luck on this one. But WA after WA.
[pascal]{$MODE DELPHI}

program p10078;
{SPOILER REMOVED}
...
if (allpositive or allnegative) then writeln('Yes') else writeln('No');
...
[/pascal]

What am I doing wrong?
My method is simple: I walk around the gallery walls and with every turn I determine if it's a right or a left turn. If I only make right turns, or only make left turns, then the gallery walls form a convex hull, and then, by definition, all points in the gallery are visible from all other points in the gallery. Right?

Please help me,

-little joey
Last edited by little joey on Fri Sep 05, 2003 10:58 pm, edited 1 time in total.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Sep 05, 2003 9:44 pm

This might be a silly comment, but haven't you switched "Yes" and "No"?
(Since if all turns are left turns (or right turns), the polygon is convex, and there are no critical points, hence "No")

(Btw: my current classification of 681 is "extremely annoying" and I've gotten loads and loads of WAs there)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Sep 05, 2003 11:04 pm

Yes Per, you're absolutely right!

I feel so ashamed for so much stupidity :oops: :oops: :oops:

How can you call this? Code blindness (like color blindness and snow blindness?)

681 _is_ extremely annoying. But there are plenty of solvers, so we must be overlooking something pretty obvious...

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Tue Jul 27, 2004 12:35 am

Any ideas why this gives WA????[cpp]#include <iostream>
#include <complex>
#include <vector>
using namespace std;

vector < complex < long long > > data;
long n, x, y;

int main(){

while(cin >> n && n){
data.resize(n);
for(long i = 0; i < n && cin >> x >> y; i++) data = complex<long long>(x, y);

data.push_back(data[0]);
data.push_back(data[1]);
data.push_back(data[2]);

bool ans = true;
for(unsigned long i = 0; i + 3 < data.size(); i++)
if( real(conj(data[i + 1] - data)*(data[i + 2] - data[i + 1]))*
real(conj(data[i + 2] - data[i + 1])*(data[i + 3] - data[i + 2])) < 0)
ans = false;
if(!ans) cout << "Yes\n";
else cout << "No\n";
}

return 0;
}
[/cpp]

diac_paul
New poster
Posts: 10
Joined: Fri Nov 05, 2004 12:07 pm
Location: Iasi, Romania
Contact:

10078 tests

Post by diac_paul » Wed Mar 16, 2005 12:23 am

Can anyone give me some data tests so I can find my mistake? For exemple what should be the output for this test:
7
3 0
6 1
7 5
5 8
3 8
2 7
2 6
8
3 0
6 1
7 5
5 8
3 8
2 7
2 6
1 5
6
3 1
5 6
4 6
3 7
2 6
1 6
5
1 1
1 5
3 5
6 7
9 5
3
1 1
2 2
2 0
4
0 0
0 1000
500 501
1000 0
4
0 0
0 1000
500 499
1000 0
0
?
I get "No Yes Yes Yes No No Yes" ( ofcourse, with breaklines ).
Is this correct? I think it's rigth. Does anybody knows some other tricky tests?

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

10078

Post by ayon » Wed Nov 09, 2005 8:35 am

i got wa's and wa's in this problem. I use the algo, if all turns are clockwise or all turns are counterclockwise, then "No", else "Yes".

Code: Select all

 cut after ac
Can anyone tell me, what's wrong, or give me some crirtical I/O ?
Last edited by ayon on Fri Nov 11, 2005 7:09 pm, edited 1 time in total.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: WA ~~ problem 10078, the art gallery

Post by tan_Yui » Wed Nov 09, 2005 1:20 pm

ayon wrote:i got wa's and wa's in this problem. I use the algo, if all turns are clockwise or all turns are counterclockwise, then "No", else "Yes".

Can anyone tell me, what's wrong, or give me some crirtical I/O ?
Hi, ayon.
Your idea is good for almost case, but in critical case, this will output incorrect answer.
I think this problem is Convex Hull problem similar to problem 10065.

If the set of coordinates makes some closed space, the output should be 'Yes'.

Following is a input which shows such a case.
Please check it. :)

Code: Select all

5
0 0
100 0
50 100
30 30
50 90
6
0 0
0 10
30 10
30 0
0 30
30 30
0
Output should be :

Code: Select all

Yes
Yes
Best regards.

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Nov 09, 2005 4:04 pm

:o oops, so this is the critical case. i didnt think of it. anyway thanx to tan_Yui very much. I'll try this problem with convex hull.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Nov 09, 2005 5:30 pm

I don't think tan_Yui's tests are correct -- they contain polygons with self-intersections (and my accepted program prints No, No.)

Simply checking whether all turns are cw or ccw is enough in this problem.
avon, your program is checking just n-1 out of n turns in the polygon. You've missed one turn.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui » Thu Nov 10, 2005 3:39 am

Hi, mf.
Oh....I might have done wrong help.
Thanks for your support, mf. And I'm sorry....avon. :cry:
And, could you show as any sample input? I want to know.

By the way, I've solved this problem with Gift-Wrapping Algorithm.
I think that, though the cw or ccw checking may be enough for this problem to get Accepted, it can't support any case such I suggested.
So, it is better to deal with the problem as Convex Hull problem than
simple cw or ccw checking.
Although it is just complicated to be implemented, my code got the CPU_time 0:00.002 as a result. So there are no need to worry about the cost.

Thank you.

Post Reply

Return to “Volume 100 (10000-10099)”