Also this test

4
0 0 2 6
2 2 4 4
4 0 6 6
6 2 8 4

My AC solution gives 12 when correct answer is 8

-

Try
3
0 0 10 10
10 0 20 10
20 0 30 10
Answer
36

try a rectangle in the negative area

May be greedy wrong?
My solution based on greedy.
Starting from p1=(1,1) we go to nearest(in x+y metric) admissible p2 and so on.
I have wa 9.

Yes!. Greedy is right.
Proof: Let p3 be another admissible point.
We have:
Dist(p1,p2)<=Dist(p1,p3)-Dist(p2,p3);
Dist(p2,n)<=Dist(p3,n)+Dist(p2,p3);
=>
Dist(p1,p2)+Dist(p2,n)<=Dist(p1,p3)+Dist(p3,n)

Edited by author 22.11.2011 14:35

Try replacing y1 with y1_ and y2 with y2_.
You will get accepted.
The same thing happened to me.

Do not use bool,the compiler may not support this

I think my code is right,but it was getting wa wa all the time.
So I started to change it.
I saw the code above,so I changed mine more and more like that.
But a surprising thing ,my code is even equal to the code above,
but it got accepted,but my still wa.
I wonder..............

my code
#include<iostream>
#include<string>
#include<memory>
using namespace std;

int main(void)
{
    long n;
    cin>>n;
       long nowy=1,i,maxy,miny,x1,y1,x2,y2;
    long dist=0;
    cin>>x1>>miny>>x2>>maxy;
    bool ok=true;
    for(i=1;i<n;++i){
         cin>>x1>>y1>>x2>>y2;
        if(y1>=maxy-1||y2<=miny+1){
            ok=false;
            break;
        }
           if(y1>=nowy){
               dist+=y1+1-nowy;
               nowy=y1+1;
        }
        else if(y2<=nowy){
              dist+=nowy-y2+1;
            nowy=y2-1;
        }
        miny=y1;
        maxy=y2;
    }
    if(ok){
        dist+=x2-2;
        //dist+=abs(y2-1-nowy);
        if(nowy>y2-1)dist+=nowy+1-y2;
        else if(nowy<y2-1)dist+=y2-1-nowy;
        cout<<dist<<endl;
    }
    else cout<<"-1"<<endl;
    return 0;
}

Now this code get AC.

my code fail on test #10 for many times
i can't see why?

#include<stdio.h>

int abs(int n)
{
 if(n>=0) return n;
 else     return -n;
}

int min(int a,int b)
{
 if(a<=b) return a;
 else     return b;
}

int main()
{
 int n,i;
 int best_u_last,best_d_last
    ,y_u_last,y_d_last
    ,x1,y1,x2,y2
    ,dx;

 scanf("%d",&n);

 scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
 y_d_last=y1;
 y_u_last=y2;
 best_u_last=x2-x1+y2-y1-4;
 best_d_last=x2-x1-2;

 for(i=1;i<n;i++)
 {
  scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

  if( (y1>=y_u_last-1) || (y2<=y_d_last+1) )
  {
   //suck!!
   best_u_last=-1;
   break;
  }
  else
  {
   //pass
   //dx
   dx=abs(x2-x1);
   //u
   best_u_last=min( best_u_last + abs(y_u_last - y2) , best_d_last + abs(y_d_last - y2 + 2) ) + dx;
   //d
   best_d_last=min( best_u_last + abs(y_u_last - y1 - 2) , best_d_last + abs(y_d_last - y1) ) + dx;
  }

  y_u_last=y2;
  y_d_last=y1;
 }

 printf("%d", best_u_last );
}

In "100>=xi ? xi >=2","i" is unless than 2.

     Note:"X1=0 Y1=0" and "Xi=Xi+1" !!!