//5 -1 -1 4 3 1 1 0 3 4 0
#include<stdio.h>
#include<math.h>
#include<Limits.h>
typedef struct
 {
  int x;
  int y;
}POINT;
POINT point[50001],a[50001],b[2], *temp, source, small;
int k;
void Find(int n)
{
  int i, mult;
  temp = &point[0];
  for(i=1; i<n; i++)
  {
    if(point[i].y < temp->y || (point[i].y==temp->y && point[i].x<temp->x))
        temp = &point[i];
  }
  return;
}
int Mult(POINT a, POINT b)
{
  return (a.x*b.y - b.x*a.y);
}
double Dis(POINT k)
{
  return sqrt((k.x)*(k.x)+(k.y)*(k.y));
}
int MultBigger(POINT a, POINT b, POINT c)
{
  POINT p, q;
  p.x = b.x-a.x;
  p.y = b.y-a.y;
  
  q.x = c.x-b.x;
  q.y = c.y-b.y;
  if(Mult(p,q) < 0) return 1;           /*叉积运算*/
  else if(Mult(p,q) > 0) return 0;
  else
  {
    if(Dis(q) > Dis(p)) return 1;
    else return 0;
  }
}
int Search(int n)
{
  int i;
  POINT temper;
  temper = source;
  for(i=0; i<n; i++)
  {
    if(point[i].x ==INT_MAX)//已检查过的点 
        continue;
    if (MultBigger(source, temper, point[i]))
    {
        temp = &point[i];
        temper = point[i];
    }
  }
  if(MultBigger(source, temper, small)) return 1;
  a[k].x=temp->x;a[k].y=temp->y;k++;
  
  source = *temp;
  temp->x = INT_MAX;
  return 0;
}
int main()
{
  int n, i, c,j,m,D,D1,D2;
  double x1,y1,x2,y2,x3,y3,x4,y4;
  double min,max;
  while(scanf("%d%d",&n,&c)!=EOF)
  {
    for(i=0; i<n; i++)
    scanf("%d", &point[i].x);
    for(i=0;i<n;i++)
    scanf("%d",&point[i].y);
    if(n==1)
    {printf("%d.000 %d.000\n",point[0].y,point[0].y);continue;}
    if(n==2)
    {
    D=point[1].x-point[0].x;D1=point[1].x-c;D2=c-point[0].x;
    x1=D1/(double)D;x2=D2/(double)D2;
    if(D!=0)
    min=max=point[0].y*x1+point[1].y*x2;
    else 
    {
     if(point[0].y>point[1].y){max=point[0].y;min=point[1].y;}
     else {max=point[1].y;min=point[0].y;}
    }
     printf("%.3lf %.3lf\n",min,max);continue;
    }
    Find(n);         /*找出最下、最右点*/
    source = *temp;
    small = *temp;
    k=0;
    k++;
    a[k].x=small.x;a[k].y=small.y;k++;
    
    temp->x =INT_MAX;
    for(i=0; i<n; i++)
    if(Search(n)) break;   /*按叉积搜索 break 时回到出发点*/
    m=0;
    for(i=1;i<k;i++)
    {
    if(c==a[i].x)
    {
     m++;b[m].x=a[i].x;b[m].y=a[i].y;
     m++;b[m].x=a[i+1].x;b[m].y=a[i+1].y;
    }  
    else if(c>a[i].x&&c<a[i+1].x||c>a[i+1].x&&c<a[i].x)
    {
     m++;b[m].x=a[i].x;b[m].y=a[i].y;
     m++;b[m].x=a[i+1].x;b[m].y=a[i+1].y;
    }  
    }
    for(i=1;i<=4;i++)
    printf("%d %d\n",b[i].x,b[i].y);
    x1=b[2].x-b[1].x;y1=b[2].y-b[1].y;
    x2=c-b[1].x;
    min=(x2*y1)/(double)x1+b[1].y;
    x3=b[4].x-b[3].x;y3=b[4].y-b[3].y;
    x2=c-b[3].x;
    max=(x2*y3)/(double)x3+b[3].y;
    printf("%.3lf %.3lf\n",min,max);
  }
}//main
/*
3 1
0 2 1
0 0 1
5 2
-1 4 1 0 4
-1 3 1 3 0
*/

• AC的同志给点数据呀！！，急救！！ (0) ecjtubaowp 2007-02-20 11:22:03