11626 - Convex Hull

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

Moderator: Board moderators

Post Reply
Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

11626 - Convex Hull

Post by Jehad Uddin » Fri Sep 04, 2009 2:35 am

Hello every one,i m getting WA in this problem, i m not sure about my process of sorting points according to angle.Pls help me,

Code: Select all

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<algorithm>
#define pi 2*acos(0.0)

using namespace std;
struct point
{
 double x,y;
};
point p[100005];
point ans[100005];
int cmp(const void *a,const void *b)
{
 point *u=(point *)a;
 point *v=(point *)b;
 double theta1,theta2;
 if((u->x-p[0].x)!=0)
 {
 theta1=atan((u->y-p[0].y)/(u->x-p[0].x));
 if(theta1<0)
 theta1=pi+theta1;
 }
 else theta1=pi/2;
 if((v->x-p[0].x)!=0)
 {theta2=atan((v->y-p[0].y)/(v->x-p[0].x));
  if(theta2<0) theta2+=pi;
 }
 else theta2=pi/2;
 
 if(theta1>theta2) 
 return 1;
 else if(theta1<theta2) 
 return -1; 
 else
 {
  if((u->x-p[0].x)*(u->x-p[0].x)+(u->y-p[0].y)*(u->y-p[0].y)>(v->x-p[0].x)*(v->x-p[0].x)+(v->y-p[0].y)*(v->y-p[0].y))
  return 1;
  else if((u->x-p[0].x)*(u->x-p[0].x)+(u->y-p[0].y)*(u->y-p[0].y)<(v->x-p[0].x)*(v->x-p[0].x)+(v->y-p[0].y)*(v->y-p[0].y))
  return -1;
  else return 1;
 }
}


int main()
{
 long long int i,j,k,l,u,v,n,t,z;
 string str1;


 while(cin>>t)
 {
 for(z=1;z<=t;z++)
 
 {
  l=0;
  cin>>n;
  for(i=0;i<n;i++)
  {
   cin>>u>>v>>str1;
   if(str1=="Y"){
   p[l].x=u,p[l].y=v;
   if(l>0)
   ans[l-1].x=p[l].x,ans[l-1].y=p[l].y;
   l++;}
  }
  for(i=1;i<l;i++)
  {
   if(p[i].x<p[0].x)
   {swap(p[i],p[0]);
    swap(ans[i-1],p[0]);
   }
   else if(p[i].x==p[0].x)
   {
    if(p[i].y<p[0].y)
    {swap(p[i],p[0]);swap(ans[i-1],p[0]);}
   }
  
  
  }
  cout<<l<<endl;
  cout<<p[0].x<<" "<<p[0].y<<endl;
  
 qsort(ans,l-1,sizeof(point),cmp);
 
 for(i=0;i<l-1;i++)
 cout<<ans[i].x<<" "<<ans[i].y<<endl;
 
 
 }

}
 return 0;
}

littlebb
New poster
Posts: 1
Joined: Mon Sep 14, 2009 10:10 pm

Re: 11626 --getting WA

Post by littlebb » Mon Sep 14, 2009 10:32 pm

I also got WA on this problem and don't know how to solve it. :(

Here is my algorithm to sort the points of Convex Hull in counter-clockwise order:
1. Sort these points by x, and choose the start point p[0]
2. Given 2 sets L and U which represent LowerHull and UpperHull respectively,
for p[1] to p[n]
{
if p.y < p[0].y, then put p into L;
else put p into U;
}
3. Now we can output the points in counter-clockwise order
(1). output p[0]
(2). output set L
(3). output set U reversely

And here is my code:

Code: Select all

/* ACM #11626 - Convex Hull */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int x, y;
} Point;

int ptscmp( const void *a, const void *b );

Point C[100005], L[100005], U[100005];

int main()
{
    char isConvexHull;
    int i, l, u; /* counter */
    int NumOfCases, n, m;

    scanf( "%d", &NumOfCases );
    while( NumOfCases-- ) {
        /* INPUT */
        scanf( "%d", &n );
        for( m=0;n>0;n-- ) {
            scanf( "%d %d %c", &C[m].x, &C[m].y, &isConvexHull );
            if( isConvexHull=='Y' ) m++;
        }

        /* Determine the start point C[0] which (x,y) is minimal */
        qsort( C, m, sizeof(Point), ptscmp );

        for( l=u=0, i=1;i<m;i++ ) {
            if( C[i].y<C[0].y )
                L[l++] = C[i];
            else
                U[u++] = C[i];
        }

        /* OUTPUT */
        printf( "%d\n%d %d\n", m, C[0].x, C[0].y );
        for( i=0;i<l;i++ )
            printf( "%d %d\n", L[i].x, L[i].y );
        for( i=u-1;i>=0;i-- )
            printf( "%d %d\n", U[i].x, U[i].y );
    }

    return 0;
}

int ptscmp( const void *a, const void *b )
{
    Point *aa = (Point*) a;
    Point *bb = (Point*) b;

    return ( aa->x != bb->x ) ? ( aa->x - bb->x ) : ( aa->y - bb->y );
}
Could anyone explain why it can't work or give me some examples?
Thanks a lot. :)

el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

Re: 11626 --getting WA

Post by el cheeto » Mon Dec 07, 2009 6:15 am

Are there some tricky cases?? I just keep getting WAs and I don't know what's going on, I need help. Thank's

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11626 --getting WA

Post by serur » Sun Apr 04, 2010 12:01 pm

The only tricky case I can think of is a rhombus:

Code: Select all

1
8
0 -2 Y
1 -1 Y
2 0 Y
1 1 Y
0 2 Y
-1 1 Y
-2 0 Y
-1 -1 Y
output is the same. And I got it AC with upper envelope + lower envelope also.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11626 --getting WA

Post by Jan » Tue Jul 06, 2010 2:41 pm

The output is not same, since the problem states that
Start with the point on the hull whose x-coordinate is minimal. If there are multiple such points, start with the one whose y-coordinate is minimal.
I am adding some cases including serur's.

Input:

Code: Select all

3
12
0 0 Y
2 0 Y
1 0 Y
3 0 Y
3 3 Y
1 3 Y
2 3 Y
3 1 Y
3 2 Y
0 1 Y
0 2 Y
0 3 Y
3
0 0 Y
1000000000 1000000000 Y
1000000000 0 Y
8
0 -2 Y
1 -1 Y
2 0 Y
1 1 Y
0 2 Y
-1 1 Y
-2 0 Y
-1 -1 Y
Output:

Code: Select all

12
0 0
1 0
2 0
3 0
3 1
3 2
3 3
2 3
1 3
0 3
0 2
0 1
3
0 0
1000000000 0
1000000000 1000000000
8
-2 0
-1 -1
0 -2
1 -1
2 0
1 1
0 2
-1 1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

ldeleuran
New poster
Posts: 2
Joined: Tue Feb 04, 2014 2:13 am

Re: 11626 - Convex Hull

Post by ldeleuran » Tue Feb 04, 2014 2:31 am

I believe that this problem is not solvable using Java.

I have solved it in C++ using an efficient method requiring one sorting and two scans through the valid points (those with 'Y'). This method solves the problem in .132 seconds of poorly optimized C++.
Using Java results in TLE.

I have made the following optimizations in Java which yield run time benefits for Java:
- Using longs to store points - this makes sorting fast (on x64 bit machines at least) although x/y access is penalized because of additional bit operations.
- Reusing a minimal-size array of longs to minimize time for allocating/deallocating memory as well as improving lookup time in this array.

By submitting partial submissions to the Online Judge I am able to parse the input in time, but I do not have enough time to sort the points. (See my code below). Since two additional scans of the points are needed to solve the problem I believe that the problem isn't solvable in Java.

Code: Select all

public class P11626 {
	private static final long[] points = new long[100000];

	public static void main(String[] args) throws IOException {
                // SCAN THE INPUT:
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int NUMBER_OF_TEST_CASES = Integer.parseInt(br.readLine());
		for(int IGNORE = 0; IGNORE < NUMBER_OF_TEST_CASES; ++IGNORE) {
			final int N = Integer.parseInt(br.readLine());
			
			// Find points:
			int pi = 0;
			for(int j = 0; j < N; ++j) {
				String line = br.readLine();
				if(line.charAt(line.length()-1) == 'N')
					continue;
				String[] parts = line.split("\\s+");
				int x = Integer.parseInt(parts[0]);
				int y = Integer.parseInt(parts[1]);
				points[pi++] = (((long)x) << 32) | (y&0x00000000ffffffffl);
			}
			
			// Sort points by x:
			Arrays.sort(points, 0, pi);

                        // REMOVED CODE SNIPPET WHICH SOLVES THE PROBLEM USING TWO SIMPLE SCANS
		}		
	}
}
EDIT!

I have improved the C++ program so much that it reached the top of the score board. I then took that program, converted it to Java and the result is a 885ms AC Java program :D

The following further optimizations were needed:
- Use read and write using large buffers.
- Handle read and write of integers manually.
- Split the sorting into upper and lower hull.
- Don't use any floating point arithmetics
- Don't use angles
- Don't try to be smart when dividing points into upper and lower hulls - Having additional comparisons to avoid computations does not necessarily yield any speed improvements.

Post Reply

Return to “Volume 116 (11600-11699)”