10078 - The Art Gallery

[likhan]

For this problem I took consecutive three points and calculated whether all the tree paired points make a left turn or right turn.

[arnsfelt]

You miss the last turn,

try:

Code: Select all

5
1 1
0 0
2 1
2 2
0 2
0

Kristoffer Hansen

[likhan]

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

[infinity]

#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....

[hank]

Convex Hull Algorithm

[little joey]

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

[Per]

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)

[little joey]

Yes Per, you're absolutely right!

I feel so ashamed for so much stupidity

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]

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]

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]

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 ?

[tan_Yui]

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]

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.

[mf]

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]

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 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.