10078  The Art Gallery
Moderator: Board moderators
10078  The Art Gallery
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.
10078
#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<GetPoint1 && 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....
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<GetPoint1 && 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....
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
10078 The Art Gallery
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
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.
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)
(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)
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
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]
#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]
10078 tests
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?
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?

 Experienced poster
 Posts: 161
 Joined: Tue Oct 25, 2005 8:38 pm
 Location: buet, dhaka, bangladesh
10078
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 ?
Code: Select all
cut after ac
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

the world is nothing but a good program, and we are all some instances of the program
Re: WA ~~ problem 10078, the art gallery
Hi, ayon.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 ?
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
Code: Select all
Yes
Yes
I don't think tan_Yui's tests are correct  they contain polygons with selfintersections (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 n1 out of n turns in the polygon. You've missed one turn.
Simply checking whether all turns are cw or ccw is enough in this problem.
avon, your program is checking just n1 out of n turns in the polygon. You've missed one turn.
Hi, mf.
Oh....I might have done wrong help.
Thanks for your support, mf. And I'm sorry....avon.
And, could you show as any sample input? I want to know.
By the way, I've solved this problem with GiftWrapping 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.
Oh....I might have done wrong help.
Thanks for your support, mf. And I'm sorry....avon.
And, could you show as any sample input? I want to know.
By the way, I've solved this problem with GiftWrapping 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.