pku2595.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct 
{
	int x, y;
}P;

P p[50010];
int bt[50010], tp[50010];
int bt_top, tp_top;
int n;
double C;

int cmp(const void *a, const void *b)
{
	P *aa = (P *)a;
	P *bb = (P *)b;
	if (aa->x != bb->x)
	{
		return aa->x - bb->x;
	}
	return aa->y - bb->y;
}

int det(int x1, int y1, int x2, int y2)
{
	return x2 * y1 - x1 * y2;
}

int cross(int a, int b, int c)
{
	return det(p[b].x - p[a].x, p[b].y - p[a].y, p[c].x - p[b].x, p[c].y - p[b].y);
}

int Eq(int x, double y)
{
	if (fabs(x - y) < 1e-6)
	{
		return 1;
	}
	return 0;
}

int main()
{
	int i;
	double ans_min, ans_max;
	P p1, p2;

	while (scanf("%d %lf", &n, &C) == 2)
	{	
		for (i = 0; i < n; i++)
			scanf("%d", &p[i].x);
		for (i = 0; i < n; i++)
			scanf("%d", &p[i].y);
		qsort(p, n, sizeof(p[0]), cmp);
	
		bt[0] = 0;
		tp[0] = 0;
		bt[1] = 1;
		tp[1] = 1;
		bt_top = 1;
		tp_top = 1;
		for (i = 0; i < n; i++)
		{
			if (cross(bt[1], 0, i) <= 0)
			{
				bt[1] = i;
			}
			if (cross(tp[1], 0, i) >= 0)
			{
				tp[1] = i;
			}
		}

		for (i = bt[bt_top] + 1; i < n; i++)
		{
			while (1)
			{
				if (cross(bt[bt_top - 1], bt[bt_top], i) >= 0)
				{
					bt_top--;
				}
				else
				{
					bt[++bt_top] = i;
					break;
				}
			}
		}
		for (i = tp[tp_top] + 1; i < n; i++)
		{
			while (1)
			{
				if (cross(tp[tp_top - 1], tp[tp_top], i) <= 0)
				{
					tp_top--;
				}
				else
				{
					tp[++tp_top] = i;
					break;
				}
			}
		}
		i = 0;
		while (i <= bt_top)
		{
			if (Eq(p[bt[i]].x , C))
			{
				ans_min = (double)p[bt[i]].y;
				break;
			}
			if (p[bt[i]].x > C)
			{
				p1 = p[bt[i - 1]];
				p2 = p[bt[i]];
				ans_min = p1.y + 1.00 * (C - p1.x) * (p2.y - p1.y) / (p2.x - p1.x - 0.00);
				break;
			}
			i++;
		}
		i = tp_top;
		while (i >= 0)
		{
			if (Eq(p[tp[i]].x , C))
			{
				ans_max = (double)p[tp[i]].y;
				break;
			}
			if (p[tp[i]].x < C)
			{
				p1 = p[tp[i + 1]];
				p2 = p[tp[i]];
				ans_max = p1.y + 1.00 * (C - p1.x) * (p2.y - p1.y) / (p2.x - p1.x - 0.00);
				break;
			}
			i--;
		}
		printf("%.3lf %.3lf\n", ans_min, ans_max);
	}
	return 0;
}