#include <iostream>
#include <algorithm>

using namespace std;

struct pt
{
	int x,y,q;
	float m;
};

bool co(pt a,pt b)
{
	if (a.q!=b.q)
		return a.q>b.q;
	return a.m<b.m;
}

bool coo(pt a,pt b)
{
	if (a.q!=b.q)
	{
		if (a.q==2)
			return a.q<b.q;
		if (b.q==2)
			return b.q<a.q;
		if (a.q==1)
			return a.q<b.q;
		if (b.q==1)
			return b.q<a.q;
		if (a.q==4)
			return a.q<b.q;
		if (b.q==4)
			return b.q<a.q;
	}
	return a.m<b.m;
}

int main()
{
	pt p[50];
  int n;
  cin>>n;
  int c=0;
  cin>>c>>c;
  while (n--)
  {
    c=0;
    bool t=0,u=0;
    while (cin>>p[c].x>>p[c].y)
    {
      if (p[c].x==0)
        break;		
      p[c].m=p[c].y*1.0/p[c].x;
      if (p[c].x>0&&p[c].y>0)
        p[c].q=1,t=1;
      if (p[c].x>0&&p[c].y<0)
        p[c].q=2;
      if (p[c].x<0&&p[c].y<0)
        p[c].q=3;
      if (p[c].x<0&&p[c].y>0)
        p[c].q=4,u=1;
      c++;
    }
    sort(p,p+c,co);
    if (t&&u)
      sort(p,p+c,coo);
    cout<<"(0,0)\n";
    for (int i=0;i<c;i++)
      cout<<"("<<p[i].x<<','<<p[i].y<<")\n";
  }
	return 0;
}

• 求test数据 (0) michael 2007-01-03 18:06:46
  • 求凸包，你的算法好像不对，没仔细看…… (0) yangguo981 2007-01-24 17:26:41