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