首页 > 代码库 > hdu4631(set与二分)
hdu4631(set与二分)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4631
Sad Love Story
Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)Total Submission(s): 1590 Accepted Submission(s): 501
Problem Description
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.
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.
Input
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.
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.
Output
For each test cases,print the answer in a line.
Sample Input
2 5 765934 377744 216263 391530 669701 475509 5 349753 887257 417257 158120 699712 268352
Sample Output
8237503125 49959926940HintIf there are two points coincide,then the distance between the closest pair is simply 0.
Source
2013 Multi-University Training Contest 3
Recommend
zhuyuanchen520 | We have carefully selected several similar problems for you: 4822 4821 4820 4819 4818
#include <iostream> #include <cstdio> #include <cstring> #include <set> #include <algorithm> #define LL long long using namespace std; const int MAXN=600000; LL Ax,Bx,Cx,Ay,By,Cy,ans,n; class Point { public: LL x,y; bool operator < (const Point &rhs) const { return x<rhs.x; } }; Point p[MAXN]; int main() { int T; while(cin>>T) { while(T--) { cin>>n>>Ax>>Bx>>Cx>>Ay>>By>>Cy; p[0].x=0; p[0].y=0; multiset<Point> S; S.clear(); for(int i=1;i<=n;i++) { p[i].x=(p[i-1].x*Ax+Bx)%Cx; p[i].y=(p[i-1].y*Ay+By)%Cy; } LL mindis; mindis=((LL) 1<<62); S.insert(p[1]); ans=0; for(int i=2;i<=n;i++) { multiset<Point>::iterator pp=S.lower_bound(p[i]),iter; for(iter=pp;iter!=S.begin();) { iter--; Point t=*iter; LL a=t.x-p[i].x; a*=a; if(a>=mindis) break; LL b=t.y-p[i].y; b*=b; mindis=min(mindis,a+b); } for(;pp!=S.end();pp++) { Point t=*pp; LL a=t.x-p[i].x; a*=a; if(a>=mindis) break; LL b=t.y-p[i].y; b*=b; mindis=min(mindis,a+b); } S.insert(p[i]); ans+=mindis; } cout<<ans<<endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。