Page 1 of 1

### 11626 - Convex Hull

Posted: 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;
}
``````

### Re: 11626 --getting WA

Posted: 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.

### Re: 11626 --getting WA

Posted: 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

### Re: 11626 --getting WA

Posted: 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.

### Re: 11626 --getting WA

Posted: 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.

### Re: 11626 - Convex Hull

Posted: 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:
for(int IGNORE = 0; IGNORE < NUMBER_OF_TEST_CASES; ++IGNORE) {

// Find points:
int pi = 0;
for(int j = 0; j < N; ++j) {
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

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.