首页 > ACM题库 > HDU-杭电 > hdu 2495 MC part deux[解题报告]hoj
2014
02-09

hdu 2495 MC part deux[解题报告]hoj

MC part deux

问题描述 :



The Dean has determined that mathies have outgrown the building that has served them so well for many years. Luckily for him, the PM has decided to stimulate the economy by funding a new math building. To maximize the stimulating effect, the construction process is outsourced to a software engineering consultant who employs agile methodologies. The building will be built first, and designed later. The Dean has some concerns about this innovative process. After all, it would be very embarrassing if the walls of the new math building failed to line up at right angles!

The Dean sneaks out one night with a tape measure to survey the last remaining grassy area on campus, where the new building will go. He drives stakes into the ground, then measures the distances between them. Afterwards, he retreats into his office to construct a map from his measurements. He notices that the first three stakes form a right-angled triangle with arms of length one metre and hypotenuse of length sqrt(2) metres. And that’s not all. The Dean plots these first three stakes on a piece of graph paper at coordinates (0,0), (0,1), and (1,0). After plotting some of the other stakes, it turns out that all of the stakes happen to be precisely at lattice points (i.e. points with integer coordinates) on the graph paper. Still, plotting all of the many stakes is tedious, so he asks his co-op student (i.e. you) to help out.

输入:

Input consists of a number of test cases. The first line of each test case contains two integers n and m, each at least 1 and no larger than 1000. The integer n is the number of lines that follow, and m is the number of stakes. The stakes are numbered from 1 to m. All of the stakes are at distinct locations. The x and y coordinates of each stake are no less than -1000000 and no greater than 1000000. Each of the following lines contains exactly six integers a, b, c, x, y, z. The integers a, b, and c are the numbers of three stakes. The three stakes are always listed in counter-clockwise order. That is, to move from stake a to stake b and then to stake c, one must turn left at stake b. The number x is the square of the distance from stake a to stake b. The number y is the square of the distance from stake b to stake c. The number z is the square of the distance from stake c to stake a. Every stake will appear in at least one line of the input. For every pair of stakes a, b, there is a subset of the triangles in the input that forms a sequence T1, T2, …, Tn such that two of the vertices of Ti are also vertices of Ti+1 for all 0 < i < n, a is a vertex of T1, and b is a vertex of Tn. The last line of input is 0 0. These zeros are not values of n and m, and should not be processed as such.

输出:

Input consists of a number of test cases. The first line of each test case contains two integers n and m, each at least 1 and no larger than 1000. The integer n is the number of lines that follow, and m is the number of stakes. The stakes are numbered from 1 to m. All of the stakes are at distinct locations. The x and y coordinates of each stake are no less than -1000000 and no greater than 1000000. Each of the following lines contains exactly six integers a, b, c, x, y, z. The integers a, b, and c are the numbers of three stakes. The three stakes are always listed in counter-clockwise order. That is, to move from stake a to stake b and then to stake c, one must turn left at stake b. The number x is the square of the distance from stake a to stake b. The number y is the square of the distance from stake b to stake c. The number z is the square of the distance from stake c to stake a. Every stake will appear in at least one line of the input. For every pair of stakes a, b, there is a subset of the triangles in the input that forms a sequence T1, T2, …, Tn such that two of the vertices of Ti are also vertices of Ti+1 for all 0 < i < n, a is a vertex of T1, and b is a vertex of Tn. The last line of input is 0 0. These zeros are not values of n and m, and should not be processed as such.

样例输入:

1 3
1 3 2 1 2 1
0 0

样例输出:

0 0
0 1
1 0

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
#define EPS 1e-8

#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))

struct tri
{
	int a,b,c;
	int x,y,z;
};

pair<int,int> findxy(int x1, int y1, int x2, int y2, double a, double b, double c)
{
	double the= acos( (a+b-c)/2 / sqrt(a) / sqrt(b));
	double x3= double(x1-x2)*sqrt(b)/sqrt(a);
	double y3= double(y1-y2)*sqrt(b)/sqrt(a);

	double x3r = x3*cos(-the) - y3*sin(-the);
	double y3r = x3*sin(-the) + y3*cos(-the);

	x3r += x2;
	y3r += y2;

	int x3i = (int) floor( x3r + 0.1);
	int y3i = (int) floor( y3r + 0.1);

	return make_pair(x3i,y3i);
}

int main()
{
	int n,m;
	cin>>n>>m;
	while(n && m)
	{
		int p[1001][2]={0};
		p[1][0]= 0; p[1][1]=0;
		p[2][0]= 0; p[2][1]=1;
		p[3][0]= 1; p[3][1]=0;
		bool set[1001]={};
		set[1]=set[2]=set[3]=1;

		tri t[1001];

		map<pair<int,int>, vector<int> > e2t;

		for(int i=1; i<=n; i++)
		{
			cin>>t[i].a>>t[i].b>>t[i].c>>t[i].x>>t[i].y>>t[i].z;

			e2t[make_pair(t[i].a,t[i].b) ].push_back(i);
			e2t[make_pair(t[i].b,t[i].a) ].push_back(i);

			e2t[make_pair(t[i].b,t[i].c) ].push_back(i);
			e2t[make_pair(t[i].c,t[i].b) ].push_back(i);

			e2t[make_pair(t[i].c,t[i].a) ].push_back(i);
			e2t[make_pair(t[i].a,t[i].c) ].push_back(i);
		}
		queue<int> que;
		que.push(*e2t[make_pair(1,2)].begin());
		bool visited_t[1001]={0};

		while(!que.empty())
		{
			int x=que.front();
			que.pop();
			visited_t[x]=1;

			if (!set[t[x].a])
			{
				pair<int,int> point;
				point = findxy( p[t[x].b][0], p[t[x].b][1], p[t[x].c][0], p[t[x].c][1],  t[x].y, t[x].z, t[x].x);
				p[t[x].a][0] = point.first;
				p[t[x].a][1] = point.second;
				set[t[x].a] = 1;
			}
			else if (!set[t[x].b])
			{
				pair<int,int> point;
				point = findxy( p[t[x].c][0], p[t[x].c][1], p[t[x].a][0], p[t[x].a][1],  t[x].z, t[x].x, t[x].y);
				p[t[x].b][0] = point.first;
				p[t[x].b][1] = point.second;
				set[t[x].b] = 1;
			}
			else if (!set[t[x].c])
			{
				pair<int,int> point;
				point = findxy( p[t[x].a][0], p[t[x].a][1], p[t[x].b][0], p[t[x].b][1],  t[x].x, t[x].y, t[x].z);
				p[t[x].c][0] = point.first;
				p[t[x].c][1] = point.second;
				set[t[x].c] = 1;
			}

			vector<int>::iterator it;
			for ( it = e2t[make_pair(t[x].a,t[x].b) ].begin(); it!=e2t[make_pair(t[x].a,t[x].b) ].end(); it++)
			{
				if (!visited_t[*it]) que.push(*it);
			}
			for ( it = e2t[make_pair(t[x].b,t[x].c) ].begin(); it!=e2t[make_pair(t[x].b,t[x].c) ].end(); it++)
			{
				if (!visited_t[*it]) que.push(*it);
			}
			for ( it = e2t[make_pair(t[x].a,t[x].c) ].begin(); it!=e2t[make_pair(t[x].a,t[x].c) ].end(); it++)
			{
				if (!visited_t[*it]) que.push(*it);
			}
		}

		for(int i=1; i<=m; i++) cout<<p[i][0]<<" "<<p[i][1]<<"\n";
		cin>>n>>m;
	}
	return 0;
}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确