## 675 - Convex Hull of the Polygon

Moderator: Board moderators

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### 675 - Convex Hull of the Polygon

I am getting continuous RTE in this simple(most probably) convex-hull problem.
Can anyone tell me what can be the number of points?
I have tried with number of points=2*10^6,but that also resulted in a RTE.
My code of convex-hull is tested , I got AC in almost 10-12 convex-hull problems of UVa.
This is my scanning part:

Code: Select all

while(scanf("%lf,%lf",&p[n].x,&p[n].y)!=EOF)
n++;
Please let me know what is my mistake.
There are only 6 persons who have solved it,but it is not that hard,is it?

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
I just got accepted. I also think this problem is not so hard, as you said.

For the input, there is only 1 polygon. The vertex number do not exceed 100. The coordinates are all integers. For the output, the sequence of convex hull's vertices can be either clockwise or counter-clockwise. Anyone is accepted.

There are many algorithms to find the convex hull of a polygon. In this problem, I used Andrew's Monotone Chain algorithm. It worked well.

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
I have noticed that this problem is not allowed for judgement in the old system. I think that the data sets for judging haven't been prepared yet. In the new system, you can got accepted even if your program prints nothing.

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA
This is a peculiar problem->must be a fault of the judge.
The following code gets AC:

Code: Select all

#include<stdio.h>

int main()
{
char s[100];
while(gets(s))
{
printf("Its ok\n");
}
return 0;
}
And my actual programme gets continuous RTE,don't know the reason.

Juanito
New poster
Posts: 4
Joined: Thu Sep 18, 2008 5:20 am

### Re: 675 - Convex Hull of the Polygon

Yes i got RTE too, when i sent the little code you posted i got AC :S

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

### Re: 675 - Convex Hull of the Polygon

Perhaps nobody cares about this topic any more, but I would really like to know the expected output of the following test cases:
1, 1
0, 0
-1, 1
-1, -1
3, -1
3, 1
2, 0
1, 1

0, 0
1, 0
1, -1
2, -1
2, 1
-1, 1
-1, -1
0, -1
0, 0
Should it be this:
-1, 1
-1, -1
3, -1
3, 1
-1, 1

2, -1
2, 1
-1, 1
-1, -1
2, -1
or this:
1, 1
-1, 1
-1, -1
3, -1
3, 1
1, 1

1, -1
2, -1
2, 1
-1, 1
-1, -1
0, -1
1, -1
or something else? Thanks.

Edit: never mind. solved.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 675 - Convex Hull of the Polygon

tobby wrote:Perhaps nobody cares about this topic any more, but I would really like to know the expected output of the following test cases:
1, 1
0, 0
-1, 1
-1, -1
3, -1
3, 1
2, 0
1, 1

0, 0
1, 0
1, -1
2, -1
2, 1
-1, 1
-1, -1
0, -1
0, 0
Should it be this:
-1, 1
-1, -1
3, -1
3, 1
-1, 1

2, -1
2, 1
-1, 1
-1, -1
2, -1
or this:
1, 1
-1, 1
-1, -1
3, -1
3, 1
1, 1

1, -1
2, -1
2, 1
-1, 1
-1, -1
0, -1
1, -1
or something else? Thanks.

Edit: never mind. solved.
My A.C. program reports following results:

Code: Select all

-1, 1
-1, -1
3, -1
3, 1
-1, 1

2, -1
2, 1
-1, 1
-1, -1
2, -1
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

volz_kz_g
New poster
Posts: 8
Joined: Sun Jan 13, 2013 3:25 pm

### 675

Does this problem have some tricks?
I use the data I can find this forum,and can get the correct answer.
But when I submit this problem,always get the WA.
Does it have something to pay attention to?

my code below:

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <complex>
#include <string>
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define rrep(i,j,k) for (int i=j;i>=k;--i)
#define x real()
#define y imag()

using namespace std;

const double eps = 1e-10;
const int maxn = 11111;
typedef complex<double> point;
typedef pair<point,int> pi;
pi p[maxn],ch[maxn];
int n,len,t;
string s,sx,sy;
istringstream ss,sxx,syy;

bool cmp(const pi & a,const pi & b)
{
point aa = a.first;
point bb = b.first;
return (aa.x == bb.x)?aa.y<bb.y:aa.x<bb.x;
}

int dblcmp(double k)
{
if (fabs(k) < eps) return 0;
if (k>0) return 1;
else return -1;
}

double cross(point & o,point & a,point & b)
{
point oa = a - o;
point ob = b - o;
return (oa.x * ob.y - oa.y * ob.x);
}

void andewMonotoneChain()
{
int uc,lc;
sort(p+1,p+n+1,cmp);
ch[1] = p[1];ch[uc = 2] = p[2];
rep(i,3,n)
{
while (uc > 1 &&
dblcmp(cross(ch[uc].first,ch[uc-1].first,p[i].first)) <= 0)
uc--;
ch[++uc] = p[i];
}
ch[lc = uc+1] = p[n-1];
rrep(i,n-2,1)
{
while (lc > uc &&
dblcmp(cross(ch[lc].first,ch[lc-1].first,p[i].first)) <= 0)
lc--;
ch[++lc] = p[i];
}
len = lc-1;
}

void print()
{
if (t != 1) cout << endl;
int pos,minNum = 0x7FFFFFFF/2;
rep(i,1,len)
if (ch[i].second < minNum)
{
minNum = ch[i].second;
pos = i;
}
rrep(i,pos,1) cout << ch[i].first.x << ", " << ch[i].first.y << endl;
rrep(i,len,pos) cout << ch[i].first.x << ", " << ch[i].first.y << endl;
}

int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
ios::sync_with_stdio(false);

while (!cin.eof())
{
t++;
n = 0;
while (getline(cin,s))
{
n++;
ss.clear();
sxx.clear();
syy.clear();
ss.str(s);
getline(ss,sx,',');
getline(ss,sy);
sxx.str(sx);
syy.str(sy);
sxx >> p[n].first.x;
syy >> p[n].first.y;
//cout << sx << "!" << sy << endl;
//cout << p[n].first.x << " " << p[n].first.y << endl;
if (cin.eof()) break;
}
n--;
andewMonotoneChain();
print();
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 675

Don't read and write to a file. For input:

Code: Select all

0, 0
2, 0
1, 1
2, 2
0, 2
0, 0

0, 0
2, 0
1, 1
2, 2
0, 2
0, 0
Output should be:

Code: Select all

0, 0
2, 0
2, 2
0, 2
0, 0

0, 0
2, 0
2, 2
0, 2
0, 0
Check input and AC output for thousands of problems on uDebug!

volz_kz_g
New poster
Posts: 8
Joined: Sun Jan 13, 2013 3:25 pm

### Re: 675

brianfry713 wrote:Don't read and write to a file. For input:

Code: Select all

0, 0
2, 0
1, 1
2, 2
0, 2
0, 0

0, 0
2, 0
1, 1
2, 2
0, 2
0, 0
Output should be:

Code: Select all

0, 0
2, 0
2, 2
0, 2
0, 0

0, 0
2, 0
2, 2
0, 2
0, 0
I change the way of reading data?
And the result is still WA?
I generate the random I/O and get the answer by myself ,
the answer my program output is right.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <complex>
#include <string>
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define rrep(i,j,k) for (int i=j;i>=k;--i)
#define x real()
#define y imag()

using namespace std;

const double eps = 1e-10;
const int maxn = 111111;
typedef complex<double> point;
typedef pair<point,int> pi;
pi p[maxn],ch[maxn];
int n,len,t;
string s,sx,sy;
istringstream ss,sxx,syy;

bool cmp(const pi & a,const pi & b)
{
point aa = a.first;
point bb = b.first;
return (aa.x == bb.x)?aa.y<bb.y:aa.x<bb.x;
}

int dblcmp(double k)
{
if (fabs(k) < eps) return 0;
if (k>0) return 1;
else return -1;
}

double cross(point & o,point & a,point & b)
{
point oa = a - o;
point ob = b - o;
return (oa.x * ob.y - oa.y * ob.x);
}

void andewMonotoneChain()
{
int uc,lc;
sort(p+1,p+n+1,cmp);
ch[1] = p[1];ch[uc = 2] = p[2];
rep(i,3,n)
{
while (uc > 1 &&
dblcmp(cross(ch[uc].first,ch[uc-1].first,p[i].first)) <= 0)
uc--;
ch[++uc] = p[i];
}
ch[lc = uc+1] = p[n-1];
rrep(i,n-2,1)
{
while (lc > uc &&
dblcmp(cross(ch[lc].first,ch[lc-1].first,p[i].first)) <= 0)
lc--;
ch[++lc] = p[i];
}
len = lc-1;
}

void print()
{
if (t != 1) cout << endl;
int pos,minNum = 0x7FFFFFFF/2;
rep(i,1,len)
if (ch[i].second < minNum)
{
minNum = ch[i].second;
pos = i;
}
rrep(i,pos,1) cout << ch[i].first.x << ", " << ch[i].first.y << endl;
rrep(i,len,pos) cout << ch[i].first.x << ", " << ch[i].first.y << endl;
}

int main()
{
ios::sync_with_stdio(false);

while (!cin.eof())
{
t++;
n = 0;
while (getline(cin,s) && s.size()!=0)
{
n++;
ss.clear();
sxx.clear();
syy.clear();
ss.str(s);
getline(ss,sx,',');
getline(ss,sy);
sxx.str(sx);
syy.str(sy);
sxx >> p[n].first.x;
syy >> p[n].first.y;
p[n].second = n;
//cout << sx << "!" << sy << endl;
//cout << p[n].first.x << " " << p[n].first.y << endl;
if (cin.eof()) break;
}
n--;
if (n<=0) continue;
//rep(i,1,n) cout << p[i].first << endl;
andewMonotoneChain();
print();
}

return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 675

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

volz_kz_g
New poster
Posts: 8
Joined: Sun Jan 13, 2013 3:25 pm

### Re: 675

brianfry713 wrote:Try solving it without using floating point.
It doesn't work.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 675 - Convex Hull of the Polygon

Test data generator:

Code: Select all

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
srand(time(NULL));

int x, y;
for (int c = 1; c <= 1000; c++)
{
if (c > 1) cout << '\n';
for (int i = 1; i <= 1000; i++)
{
x = rand() % 1000 * (rand() % 2 == 0 ? 1 : -1);
y = rand() % 1000 * (rand() % 2 == 0 ? 1 : -1);
cout << x << ", " << y << '\n';
if (rand() % 100 >= 60) cout << x << ", " << y << '\n';
}
}

return 0;
}