pku2695.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 87 行

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

typedef struct 
{
	double x;
	double y;
} Point;

Point p[100], dis, lasdis;

double dot(Point a, Point b, Point c)
{
	return a.x * (c.x - b.x) + a.y * (c.y - b.y);
}

double Dot(Point a, Point b, Point c)
{
	return (c.x - b.x) * (b.x - a.x) + (c.y - b.y) * (b.y - a.y);
}

double calcdis(Point a, Point b)
{
	return sqrt( (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}

int main()
{
	double D, nextcos, tmpcos, tmpdis, tmpdot;
	int N, S, i, j, nextid;
	
//	freopen("2695.in", "r", stdin);
	while (scanf("%lf %lf %d %d %lf", &dis.x, &dis.y, &N, &S, &D) != -1)
	{
		lasdis.x = dis.x;
		lasdis.y = dis.y;
		if (fabs(dis.x) < 1e-6 && fabs(dis.y) < 1e-6 && N == 0 && S == 0 && fabs(D) < 1e-6)
		{
			break;
		}
		for (i = 0; i < N; i++)
		{
			scanf("%lf %lf", &p[i].x, &p[i].y);
		}

		do
		{
			printf("%d ", S);
			S--;
			nextid = -1;
			nextcos = 0;
			for (i = 0; i < N; i++)
			{
				if (i == S)
				{
					continue;
				}

				tmpdis = calcdis(p[S], p[i]);
				tmpdot = dot(dis, p[S], p[i]);
				tmpcos = tmpdot / tmpdis;

				if (tmpdot <= 0 || tmpdis > D || dot(lasdis, p[S], p[i]) < 0)
				{
					continue;
				}
				if (tmpcos > nextcos)
				{
					nextcos = tmpcos;
					nextid = i;
				}
			}
			if (nextid == -1)
			{
				break;
			}
			lasdis.x = p[nextid].x - p[S].x;
			lasdis.y = p[nextid].y - p[S].y;
			S = nextid + 1;
		}
		while (nextid != -1);
		printf("\n");
	}
	return 0;
}