首页 > ACM题库 > HDU-杭电 > HDU 4631-Sad Love Story[解题报告]HOJ
2015
09-17

HDU 4631-Sad Love Story[解题报告]HOJ

Sad Love Story

问题描述 :

There’s a really sad story.It could be about love or about money.But love will vanish and money will be corroded.These points will last forever.So this time it is about points on a plane.
We have a plane that has no points at the start.
And at the time i,we add point pi(xi, yi).There is n points in total.
Every time after we add a point,we should output the square of the distance between the closest pair on the plane if there’s more than one point on the plane.
As there is still some love in the problem setter’s heart.The data of this problem is randomly generated.
To generate a sequence x1, x2, …, xn,we let x0 = 0,and give you 3 parameters:A,B,C. Then xi = (xi-1 * A + B) mod C.
The parameters are chosen randomly.
To avoid large output,you simply need output the sum of all answer in one line.

输入:

The first line contains integer T.denoting the number of the test cases.
Then each T line contains 7 integers:n Ax Bx Cx Ay By Cy.
Ax,Bx,Cx is the given parameters for x1, …, xn.
Ay,By,Cy is the given parameters for y1, …, yn.
T <= 10.
n <= 5 * 105.
104 <= A,B,C <= 106.

输出:

The first line contains integer T.denoting the number of the test cases.
Then each T line contains 7 integers:n Ax Bx Cx Ay By Cy.
Ax,Bx,Cx is the given parameters for x1, …, xn.
Ay,By,Cy is the given parameters for y1, …, yn.
T <= 10.
n <= 5 * 105.
104 <= A,B,C <= 106.

样例输入:

2
5 765934 377744 216263 391530 669701 475509
5 349753 887257 417257 158120 699712 268352

样例输出:

8237503125
49959926940
Hint
If there are two points coincide,then the distance between the closest pair is simply 0.

题目大意是说给你坐标的计算公式xi=(xi-1*A+B)%C(y计算相同,只是注意A、B、C值的不同),然后可以得到n个坐标,题目是说在平面上添加坐标,每添加一个坐标则计算平面上2坐标间的最小值,然后要求输出所有最小值的和。按照题目要求,按1-n的顺序添加点

STL 标准模板库过的~没什么说的,时间耗费比较大

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
using namespace std;
const int maxn=501000;
const long long inf=1LL<<60;
struct Point
{
    long long x;
    long long y;
    bool operator < (const Point& a)const
    {
	if(x==a.x)
	    return y<a.y;
	return x<a.x;
    }
};
multiset<Point> s;
multiset<Point>::iterator it,k;
int n;
long long ax,ay,bx,by,cx,cy,x[maxn],y[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
	scanf("%d",&n);
	scanf("%I64d%I64d%I64d",&ax,&bx,&cx);
	scanf("%I64d%I64d%I64d",&ay,&by,&cy);
	x[0]=y[0]=0;
	for(int i=1;i<=n;i++)
	{
	    x[i]=(x[i-1]*ax+bx)%cx;
	    y[i]=(y[i-1]*ay+by)%cy;
	}
	Point p;
	p.x=x[1];
	p.y=y[1];
	s.clear();
	s.insert(p);
	long long ans=0,mini=inf;
	for(int i=2;i<=n;i++)
	{
	    p.x=x[i];
	    p.y=y[i];
	    it=s.lower_bound(p);
	    for(k=it;k!=s.end();k++)
	    {
		long long itx=p.x-k->x;
		itx*=itx;
		if(mini<=itx)
		    break;
		long long ity=p.y-k->y;
		ity*=ity;
		mini=min(mini,itx+ity);
	    }
	    for(k=it;k!=s.begin();)
	    {
		k--;
		long long itx=p.x-k->x;
		itx*=itx;
		if(mini<=itx)
		    break;
		long long ity=p.y-k->y;
		ity*=ity;
		mini=min(mini,itx+ity);
	    }
	    ans+=mini;
	    s.insert(p);
	}
	printf("%I64d\n",ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/z309241990/article/details/9970789