Poj Solution 2595

http://poj.org/problem?id=2595

#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

/////////////////////////
#define Type double /*�������*/
/////////////////////////


struct point
{Type x,y;
point(){x=y=0;}
point(Type &x,Type &y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};

struct line
{point a,b;
line(){;}
line(point &x,point &y):a(x),b(y)
{;}
};

const double pi=3.14159265359;

inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}
/////////////////////////////////////////////////////////////

point crosspoint(line l1,line l2)
{Type p1=cheng(l2.a,l1.a,l2.b),
      p2=cheng(l2.a,l2.b,l1.b);
if(p1+p2==0)return l1.a;

point c;
c.x=(p1*l1.b.x+p2*l1.a.x)/(p1+p2);
c.y=(p1*l1.b.y+p2*l1.a.y)/(p1+p2);
return c;
}

/////////////////////////////////////////////////////////
int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}

void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}


/////////////////////////////////////////////////////
#define CONVEX_SIZE 50000
int stack[CONVEX_SIZE],sign[CONVEX_SIZE];


int convex(point *p,int n,point *wall)
{int i;int st;Type h;

if( n < 3 )
{
    for( i=0; i<n; i++ )
    wall[i] = p[i];
     return n;
 }    

st=0;
stack[st++]=0;
stack[st++]=1;

for(i=0;i<n;i++)sign[i]=0;

sign[1]=1;
i=2;

while(i<n)
    {while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))/**/ > /**/ 0)
                                                         //��͹�����Ҳ�㣬use '>'
            {st--;if(h)sign[stack[st]]=0;}
    stack[st++]=i;sign[i]=1;i++;
    }

i--;

while(i>=0)
    {while(sign[i])i--;
    
     while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])/**/ > /**/ 0)st--;
     
     stack[st++]=i;
     i--;
    }
st--;
if(wall){for(i=0;i<st;i++)wall[i]=p[stack[i]];}
return st;
}
/////////////////////////////////
point p[50001], pt[50001];
int n,c;
void doit()
{
    int i, j;
    double up=-10000, down=10000, s;   
    sort( p, n );
    n = convex( p, n, pt );    
    for( i=0; i<n; i++ )
    {
        j = ( i==n-1 ? 0 : i+1 );        
        if( pt[i].x == c ) s = pt[i].y;
        else if( ( pt[i].x - c ) * ( pt[j].x - c ) < 0 )
            s = pt[i].y + ( c - pt[i].x ) * ( pt[j].y - pt[i].y ) / ( pt[j].x - pt[i].x );
        else continue;            
        if( up < s ) up = s;
        if( down > s ) down = s;
    }    
    printf( "%.3lf %.3lfn", down, up );
}
bool init()
{
    int i;
    if( scanf( "%d %d", &n, &c ) != 2 )
    return false;
    
    for( i=0; i<n; i++ )
    scanf( "%lf", &p[i].x );
    
    for( i=0; i<n; i++ )
    scanf( "%lf", &p[i].y );
    
    return true;
}
int main()
{
    while( init() )
        doit();   
    return 0;
}