Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
I have got WA,but I do not know why? faint.......In Reply To:谁能告诉我,为什么WA? Posted by:kikif at 2007-09-03 11:31:15 > #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; > }*/ > } > > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator