## 11072 - Points

Moderator: Board moderators

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: WA, Need some testcases

Ecou wrote:I get WA, and i can't find a testcase where output isn't what i expect,
so looking for bugs/critical input.
Doesn't work for this one:

Code: Select all

``````29
0 0
10 0
0 10
-11 11
-12 12
-13 13
-14 14
-5 5
-20 20
-18 18
-6 6
-22 22
-23 23
-15 15
-27 27
-28 28
-7 7
-8 8
-19 19
-24 24
-25 25
-26 26
-9 9
-10 10
-16 16
-21 21
-29 29
-30 30
-17 17
25
-29 29
-29 28
-29 27
-29 26
-29 25
-28 29
-28 28
-28 27
-28 26
-28 25
-27 29
-27 28
-27 27
-27 26
-27 25
-26 29
-26 28
-26 27
-26 26
-26 25
-25 29
-25 28
-25 27
-25 26
-25 25``````
The correct output:

Code: Select all

``````inside
outside
outside
outside
outside
outside
inside
outside
outside
outside
outside
inside
inside
outside
outside
outside
outside
inside
inside
outside
outside
outside
outside
inside
inside``````

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

### Re: Those all pass.

Ecou wrote:You have a double point (2,2) in the first testcases for set1. if i remove
that i get the exact same output. Got any more?
no

Ecou
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

### OK

Thanks Martin.

I was too stupid to sort correctly. Proud owner of the slowest solution now.

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### WHY WA??

Hi,
I'm trying to solve 11072 and am getting WA.
My idea:
Compute the convex hull. Then, to check if the points lie inside the hull, check if the absolute value of the sum of areas formed by the triangle and 2 points of the hull is equal to the area of the convex hull. Is this correct? I think so, because i pass all the cases in the threads.
Here's the code:

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
#include<complex>
using namespace std;

template  <class type1> type1 cross(const complex <type1>  &a, const complex <type1>  &b) { return imag(conj(a) * b); }
bool polarcmp(const complex <int> &a,const complex<int> &b){return cross(a,b)>0;}
bool cmp(const complex <int>  &a, const complex <int>  &b)
{
if(a.imag()==b.imag())
return a.real()<b.real();
else
return a.imag()<b.imag();
}
template < class type1> vector<complex<type1> > convexhull(const vector<complex<type1> > & arg1)
{
vector<complex <type1> > v=arg1;
sort(v.begin(),v.end(),cmp);
complex<type1> p=v[0];
for(unsigned i=0;i<v.size();i++)
v[i]-=p;
stable_sort(v.begin()+1,v.end(),polarcmp);
vector<complex<type1> > s;
s.push_back(v[0]);
s.push_back(v[1]);
for(unsigned  i=2;i<v.size();i++)
{
while(s.size()>=2 && cross(s.back()-s[s.size()-2],v[i]-s.back())<=0)
s.pop_back();
s.push_back(v[i]);
}
for(unsigned i=0;i<s.size();i++)
s[i]+=p;
return s;
}
template<class type1> type1 area(vector<complex<type1> > p)
{
type1 sum=0;
for(unsigned  i=1;i<p.size()-1;i++)
{
sum+=cross(p[i]-p[0],p[i+1]-p[0]);
}
return sum;
}

int main()
{
int n;
cin>>n;
vector<complex<int> > v(n);
for(int i=0;i<n;i++)
{
int a,b;
scanf(" %d %d",&a,&b);
v[i]=complex<int>(a,b);
}
vector<complex<int> > chull=convexhull(v);
int checkarea=area(chull);
int p;
cin>>p;
for(int i=0;i<p;i++)
{
int x,y;
scanf(" %d %d",&x,&y);
int testarea=0;
for(int j=0;j<chull.size();j++)
{
vector<complex<int> > a(3);
a[0]=complex<int> (x,y);
a[1]=chull[j];
a[2]=chull[(j+1)%chull.size()];
int t=area(a);
testarea+=(t>=0?t:-t);
}
if(checkarea==testarea)
printf("inside\n");
else
printf("outside\n");
}

return 0;
}
``````

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### Why WA??

Perhaps the last solution is a bit slow. But I see no reason why it shouldnt be correct. Anyway, here's the new solution. Please Please give me test cases where my program fails or point out the mistake in my code.

ranban282
New poster
Posts: 37
Joined: Tue May 02, 2006 1:01 pm
Contact:

### Why WA??

Perhaps the last solution is a bit slow. But I see no reason why it shouldnt be correct. Anyway, here's the new solution. Please Please give me test cases where my program fails or point out the mistake in my code.
Here goes:

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<list>
#include<queue>
#include<cctype>
#include<stack>
#include<map>
#include<set>
#include<complex>
using namespace std;
template  <class type1> type1 cross(const complex <type1>  &a, const complex <type1>  &b) { return imag(conj(a) * b); }
bool polarcmp(const complex <int> &a,const complex<int> &b){return cross(a,b)>0;}
bool cmp(const complex <int>  &a, const complex <int>  &b)
{
if(a.imag()==b.imag())
return a.real()<b.real();
else
return a.imag()<b.imag();
}
template < class type1> vector<complex<type1> > convexhull(const vector<complex<type1> > & arg1)
{
vector<complex <type1> > v=arg1;
sort(v.begin(),v.end(),cmp);
complex<type1> p=v[0];
for(unsigned i=0;i<v.size();i++)
v[i]-=p;
stable_sort(v.begin()+1,v.end(),polarcmp);
vector<complex<type1> > s;
s.push_back(v[0]);
s.push_back(v[1]);
for(unsigned  i=2;i<v.size();i++)
{
while(s.size()>=2 && cross(s.back()-s[s.size()-2],v[i]-s.back())<=0)
s.pop_back();
s.push_back(v[i]);
}
for(unsigned i=0;i<s.size();i++)
s[i]+=p;
return s;
}
template<class type1> type1 area(vector<complex<type1> > p)
{
type1 sum=0;
for(unsigned  i=1;i<p.size()-1;i++)
sum+=cross(p[i]-p[0],p[i+1]-p[0]);
return sum;
}

int main()
{
int n;
cin>>n;
vector<complex<int> > v(n);
for(int i=0;i<n;i++)
{
int a,b;
scanf(" %d %d",&a,&b);
v[i]=complex<int>(a,b);
}
vector<complex<int> > chull=convexhull(v);
/*for(int i=0;i<chull.size();i++)
{
cout<<chull[i]<<endl;
}*/
int p;
cin>>p;
for(int i=0;i<p;i++)
{
int x,y;
scanf(" %d %d",&x,&y);
int low=1;
int high=chull.size()-2;
complex<int> temp=complex<int>(x,y)-chull[0];
int flag=0;
while(low<=high)
{
if(temp.imag()<0)
break;
int mid=(low+high)/2;

//cout<<mid<<temp<<endl;
if(cross(chull[mid]-chull[0],temp)>=0 && cross(chull[mid+1]-chull[0],temp)<=0)
{
//cout<<mid<<endl;
if(cross(chull[mid+1]-chull[mid],complex<int>(x,y)-chull[mid])>=0)
{
flag=1;
}
break;
}
else if(cross(chull[mid]-chull[0],temp)>=0)
{
low=mid+1;
}
else
high=mid-1;
}
printf("%s\n",flag?"inside":"outside");

}

return 0;
}
``````

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
mf wrote:
then see if the point is inside the polygon or not with O(n).
You can do that in O(log n) time using binary search. Convex hull is a convex polygon, think about it.
Hi mf. I can't see how could I determine if a point is inside a convex polygon in only O(log n). I know I can do it in O(n) by traversing two successive vertices and checking if the given point is always left or right of the segment created by the two vertices. But, as I said, it requires to travel around the complete polygon and thus visit each side once, which gives me O(n).

Can you explain me how can I reduce the time to O(log n)?

Thanks a lot for your help.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
One algorithm is to take any point O inside the polygon (or one of its vertices), and sort polygon's vertices (let's call them P1, P2, ..., Pn) around it by angle. The polygon is convex, so it can be split around point O into a union of non-overlapping triangles: O P1 P2, O P2 P3, ... O Pn P1.
You can use binary search to find in which triangle a given point can possibly be, by its angle, and then check whether it actually is in that triangle. Time - O(log n) to find the triangle + O(1) to check.

This algorithm works, in general, for any star-shaped polygon - those polygons in which there's a point O, from which one can "see" all interior area of the polygon.

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia
Thanks for you answer, mf. It's very well explained
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

reynaldo_ch
New poster
Posts: 1
Joined: Fri Nov 27, 2009 10:34 pm

### Re: 11072 - Points

please some critical testcases, my program run for all testcases and get WA .