675 - Convex Hull of the Polygon

[Anindya]

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]

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]

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]

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.
Thanks for ur reply DJWS.

[Juanito]

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

[tobby]

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]

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

[volz_kz_g]

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]

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

[volz_kz_g]

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]

Try solving it without using floating point.

[volz_kz_g]

Try solving it without using floating point.

It doesn't work.

[metaphysis]

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