11072 - Points

[Martin Macko]

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]

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]

Thanks Martin.

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

[ranban282]

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]

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]

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]

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.

[mf]

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]

Thanks for you answer, mf. It's very well explained

[reynaldo_ch]

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