# 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;
}

```
This entry was posted in poj. Bookmark the permalink.