Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这题很水

Posted by witstorm at 2018-01-22 18:38:27 on Problem 1034
思路:1、计算每段路上狗能够在规定条件下访问到的兴趣点,存储之;
2、对可访问的兴趣点少的路段优先访问,然后把取到的兴趣点从其他路段中剔除

为什么这么做,道理很简单,因为选择少所以优先取喽,虽然感觉不太对,但是AC了,附代码。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
struct point{
	int x, y;
};

point master[101];
int n;
point interesting_place[101];
int m;
point result[202];
int visited[202];

struct node{
	int number;
	int seq[101];
	int count;
};
node acc[101];

bool cmp(const node a, const node b)
{
	return a.count > b.count;
}

int main()
{
	float distance_dog, distance_master;
	int count = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d", &(master[i].x), &(master[i].y));
	}
	for (int i = 0; i < m; ++i)
	{
		scanf("%d%d", &(interesting_place[i].x), &(interesting_place[i].y));
	}
	for (int i = 0; i < n - 1; ++i)
	{
		distance_master = (master[i].x - master[i + 1].x) * (master[i].x - master[i + 1].x)
			+ (master[i].y - master[i + 1].y) * (master[i].y - master[i + 1].y);
		distance_master = sqrt(distance_master);
		acc[i].count = 0;
		acc[i].number = i;
		for (int j = 0; j < m; ++j)
		{
			distance_dog = sqrt((master[i].x - interesting_place[j].x) * (master[i].x - interesting_place[j].x)
				+ (master[i].y - interesting_place[j].y) * (master[i].y - interesting_place[j].y))
				+ sqrt((master[i + 1].x - interesting_place[j].x) * (master[i + 1].x - interesting_place[j].x)
				+ (master[i + 1].y - interesting_place[j].y) * (master[i + 1].y - interesting_place[j].y));
				if (distance_dog / distance_master <= 2)
				{
					acc[i].seq[acc[i].count] = j;
					++acc[i].count;
				}
		}
	}
	for (int i = 0; i < n - 1;)
	{
		std::sort(acc, acc + n - 1 - i, cmp);
		int pos = n - 2 - i;
		while (acc[pos].count == 0 && pos >= 0)
		{
			result[acc[pos].number * 2] = master[acc[pos].number];
			visited[acc[pos].number * 2] = 1;
			count++;
			--pos;
			i++;
		}
		if (pos == -1)
		{
			break;
		}
		//i--;
		if (acc[pos].count)
		{
			int number = acc[pos].seq[acc[pos].count - 1];
			result[acc[pos].number * 2] = master[acc[pos].number];
			visited[acc[pos].number * 2] = 1;
			count++;
			result[acc[pos].number * 2 + 1] = interesting_place[number];
			visited[acc[pos].number * 2 + 1] = 1;
			acc[pos].count = 0;
			count++;
			--pos;
			i++;
			for (int j = 0; j <= pos; ++j)
			{
				for (int k = 0; k < acc[j].count; ++k)
				{
					if (acc[j].seq[k] == number)
					{
						acc[j].seq[k] = acc[j].seq[acc[j].count - 1];
						acc[j].count--;
						break;
					}
				}
			}
		}
	}
	result[(n - 1) * 2] = master[n - 1];
	count++;
	visited[(n - 1) * 2] = 1;
	std::cout << count << std::endl;
	for (int i = 0; i <= (n - 1) * 2; ++i)
	{
		if (visited[i])
		{
			printf("%d %d ", result[i].x, result[i].y);
		}
	}
	std::cout << std::endl;
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator