#include <iostream>
#include <fstream>
using namespace std;

struct point{
	double x,y;
	char xstr[50],ystr[50];
	void print(){
		cout<<"("<<xstr<<","<<ystr<<")";
	}
} p[10010];
int pn;

void swap(point &a,point &b){
	point tmp=a;
	a=b;
	b=tmp;
}

double xmult(point p1,point p2,point p0){
	return ( (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) );
}
double delt(double x1,double y1,double x2,double y2){
	return (x1*y2-x2*y1);
}

int cmp(const void *a1,const void *a2){
	point p1=*(point *)a1;point p2=*(point *)a2;
	double tmp=xmult(p1,p2,p[0]);
	if(tmp==0){
		return (p2.x*p2.x+p2.y*p2.y-p1.x*p1.x-p1.y*p1.y);
	}
	return tmp;
}



void init(){
	int root=0,i,j,k;
	for(i=1;i<pn;i++){
		if(p[i].y<p[root].y||p[i].y==p[root].y&&p[i].x<p[root].x){
			root=i;
		}
	}
	swap(p[0],p[root]);
	qsort(&p[1],pn-1,sizeof(p[1]),cmp);

	int tmp=2;
	for(i=2;i<pn;i++){
		if(xmult(p[i],p[i-1],p[0])!=0){
			p[tmp++]=p[i];
		}
	}
	pn=tmp;

}

void convex(){

	int stack[1000];
	int sn=0,i,j,k;
/*	for(i=0;i<pn;i++){
		cout<<p[i].x<<" "<<p[i].y<<endl;
	}
	cout<<endl;*/
	stack[sn++]=0;
	stack[sn++]=1;
	stack[sn++]=2;
	for(i=3;i<pn;i++){
		int a=stack[sn-1],b=stack[sn-2];
		while(xmult(p[i],p[a],p[b])<=0){
			sn--;
			a=stack[sn-1];b=stack[sn-2];
		}
		stack[sn++]=i;
	}
	p[stack[0]].print();
	for(i=sn-1;i>=0;i--){
		cout<<" ";
		p[stack[i]].print();
	}
	cout<<endl;

}



void main(){
//	ifstream cin("data.txt");
	while(1){
		char str[1000];
		cin.getline(str,1000);
		if(str[0]=='\0')break;
		int len=strlen(str);
		int i,curn=0;
		pn=0;

		char curarr[100];
		double ln,rn;
		bool turnl=false;bool turnr=false;
		for(i=0;i<len;i++){
			if(!turnl&&!turnr){
				if(str[i]=='('){
					turnl=true;
				}else{
					continue;
				}
			}else if(turnl){
				if(str[i]==','){
					curarr[curn]='\0';
					turnl=false;
					turnr=true;
					ln=atof(curarr);
					p[pn].x=ln;
					strcpy(p[pn].xstr,curarr);
			
					curarr[0]='\0';
					curn=0;
				}else{
					curarr[curn++]=str[i];
				}
			}else if(turnr){
				if(str[i]==')'){
					curarr[curn]='\0';
					turnr=false;		
					turnl=false;
					rn=atof(curarr);
					p[pn].y=rn;
					strcpy(p[pn].ystr,curarr);

					pn++;
					curarr[0]='\0';
					curn=0;
				}else{
					curarr[curn++]=str[i];
				}
			}
		}
		init();
		if(pn>=3){
			convex();
		}else{
			p[0].print();cout<<" ";p[1].print();cout<<" ";p[0].print();cout<<endl;
		}
	/*	for(i=0;i<pn;i++){
			cout<<p[i].x<<" "<<p[i].y<<endl;
		}*/
	}

}

• I have got WA,but I do not know why? faint....... (2891) ecjtunh 2007-09-16 17:51:42
• Re:谁能告诉我，为什么WA？ (253) caogtaa 2007-09-24 10:11:55