HPU暑假积分赛一之平行线

HPU暑假积分赛一之平行线

暑假第一场积分赛 *实力被捶 * 平常打的比赛很少 看来以后确实需要参加一些网赛 学长出的题真是能够锻炼心态 首先心态真的很重要 人生中第一篇博客 写的可能不是很好 请各位DL赐教

题目传送

G. 平行线
单点时限: 2.0 sec

内存限制: 512 MB

“大猩猩为什么不喜欢平行线？”“因为平行线没有相交”
哈哈哈哈哈哈哈哈哈

为了管理动物园不听话的大猩猩们，动物管理员Boctorio 决定去远方的ACM之城找一些平行线，当他逛到一个神奇的店铺时，他发现了一副黑色的图，上面依稀可见一些白色的点。Boctorio 询问店铺老板这幅画是什么，老板说：“天机不可泄露”。等Boctorio仔细端详了一会这幅画后，他惊讶的发现其中所蕴含的奥秘。向店铺老板道谢后，他拿着刚买的这幅画，就连忙赶回动物园。

输入格式
输入一个数 n(1≤n≤1000)，表示点的个数。
接下来n行，每行两个整数 xi,yi(1≤xi,yi≤109),表示第i个点。
数据保证没有重复的点

输出格式
输出用这些点所能表示出来的平行线段的对数。（两条不同的线段重合也算为平行）

样例
input
6
0 0
1 0
1 1
3 1
3 3
5 4
output
10
说一下思路 首先你可以用结构体存一下节点 之后遍历每两个节点连线的斜率 与X轴Y轴平行的是时候要特殊考虑，用map将不同的斜率出现的次数存放起来 如果同一斜率出现了N次 那对数就是N*(N-1)/2了，之后求和就行了
看代码吧 里面还有注释

#include<cstdio>
#include<iostream>
#include<cmath>
#include<map>
#include<algorithm> 

using namespace std;

typedef long long ll;

int GCD(int a,int b)
{
	return b?GCD(b,a%b):a;
}
struct node//存放点 
{
	int x;
	int y;
	bool operator<(const node &b)const
	{
		if(x!=b.x)
		return x<b.x;
		return y<b.y;
	}
}n[1200];
int main()
{
	int N;
	while(~scanf("%d",&N))
	{
		int i,j,k;
		node jie;
		map<node,int>M;//存放斜率出现的次数 
		map<node,int>::iterator it;
		for(i=0;i<N;i++)
		{
			scanf("%d%d",&n[i].x,&n[i].y);	
		}
		int A=0,B=0;//记录与X Y平行的个数
		for(i=0;i<N-1;i++)
		{
			for(j=i+1;j<N;j++)
			{
				int X,Y;
				X=n[i].x-n[j].x;
				Y=n[i].y-n[j].y;//把不同的斜率存起来Y/X;
				int gcd=GCD(abs(X),abs(Y));
				X/=gcd;
				Y/=gcd;
				if(X==0||Y==0)//考虑与X轴和Y轴平行的情况 
				{
					if(X==0)
					A++;
					else
					B++;
					continue; 
				}
				if(X*Y<0)
				jie.x=-abs(X);
				else
				jie.x=abs(X);
				jie.y=abs(Y);
				M[jie]++;
			}
		}
		int sum=0;
		for(it=M.begin();it!=M.end();it++)
		{
			int num=it->second;
			sum+=(num*(num-1)/2);
		} 
		A=A*(A-1)/2;
		B=B*(B-1)/2;
		printf("%dn",sum+A+B);
	}
	return 0;
}

最后

以上就是英俊往事为你收集整理的HPU暑假积分赛一之平行线的全部内容，希望文章能够帮你解决HPU暑假积分赛一之平行线所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。