Page 2 of 2

Re: WA, Need some testcases

Posted: Fri Sep 01, 2006 3:39 pm
by Martin Macko
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

Re: Those all pass.

Posted: Fri Sep 01, 2006 3:46 pm
by StatujaLeha
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

OK

Posted: Fri Sep 01, 2006 4:16 pm
by Ecou
Thanks Martin.

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

WHY WA??

Posted: Mon Mar 12, 2007 3:48 pm
by 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;
}

Why WA??

Posted: Sat Mar 24, 2007 5:12 pm
by 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.

Why WA??

Posted: Sat Mar 24, 2007 5:13 pm
by 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;
}

Posted: Sun Feb 24, 2008 6:45 pm
by andmej
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.

Posted: Sun Feb 24, 2008 7:31 pm
by 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.

Posted: Tue Feb 26, 2008 7:15 pm
by andmej
Thanks for you answer, mf. It's very well explained :D

Re: 11072 - Points

Posted: Fri Nov 27, 2009 10:45 pm
by reynaldo_ch
please some critical testcases, my program run for all testcases and get WA :cry: .