11072 - Points

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
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

Post by Martin Macko » Fri Sep 01, 2006 3:39 pm

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.

Post by StatujaLeha » Fri Sep 01, 2006 3:46 pm

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

Post by Ecou » Fri Sep 01, 2006 4:16 pm

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

Post by ranban282 » Mon Mar 12, 2007 3:48 pm

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

Post by ranban282 » Sat Mar 24, 2007 5:12 pm

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

Post by ranban282 » Sat Mar 24, 2007 5:13 pm

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;
}

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Sun Feb 24, 2008 6:45 pm

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:

Post by mf » Sun Feb 24, 2008 7:31 pm

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.

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Post by andmej » Tue Feb 26, 2008 7:15 pm

Thanks for you answer, mf. It's very well explained :D
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

Post by reynaldo_ch » Fri Nov 27, 2009 10:45 pm

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

Post Reply

Return to “Volume 110 (11000-11099)”