创意产品网站,撤销网站备案申请书,微信公众号分享wordpress,wordpress使用置顶文章没用http://acm.hdu.edu.cn/showproblem.php?pid4631 题意: 在平面内依次加点,求每次加点后最近点对距离平方的和 因为是找平面最近点对...所以加点以后这个最短距离一定是递减的...所以最后会形成这样一个函数图像 所以我们只要从后往前依次删点即可... 15秒惊险水过...不过我最小…http://acm.hdu.edu.cn/showproblem.php?pid4631 题意: 在平面内依次加点,求每次加点后最近点对距离平方的和 因为是找平面最近点对...所以加点以后这个最短距离一定是递减的...所以最后会形成这样一个函数图像 所以我们只要从后往前依次删点即可... 15秒惊险水过...不过我最小点对的木板肯定写挂了,卡时限的话估计过不了... 请用G交...C会TLE...当然我也无法解释这个问题...估计是我傻逼 /********************* Template ************************/
#include set
#include map
#include list
#include cmath
#include ctime
#include deque
#include queue
#include stack
#include bitset
#include cstdio
#include string
#include vector
#include cassert
#include cstdlib
#include cstring
#include sstream
#include fstream
#include numeric
#include iomanip
#include iostream
#include algorithm
#include functional
using namespace std;#define EPS 1e-8
#define MAXN (int)5e55
#define MOD (int)1e97
#define PI acos(-1.0)
#define INF ((1LL)50)
#define max(a,b) ((a) (b) ? (a) : (b))
#define min(a,b) ((a) (b) ? (a) : (b))
#define max3(a,b,c) (max(max(a,b),c))
#define min3(a,b,c) (min(min(a,b),c))
#define BUG coutBUG! endl
#define LINE cout------------------endl
#define L(t) (t 1)
#define R(t) (t 1 | 1)
#define Mid(a,b) ((a b) 1)
#define lowbit(a) (a -a)
#define FIN freopen(out.txt,w,stdout)
#pragma comment (linker,/STACK:102400000,102400000)// typedef long long LL;
// typedef unsigned long long ULL;
typedef __int64 LL;
// typedef unisigned __int64 ULL;
// int gcd(int a,int b){ return b?gcd(b,a%b):a; }
// int lcm(int a,int b){ return a*b/gcd(a,b); }/********************* F ************************/
struct point
{LL x,y;int pos;int id;point(double a 0,double b 0,int c 0){x a ; y b ; pos c;}
}p[MAXN],t[MAXN],tmp[MAXN];LL n,ax,bx,cx,ay,by,cy;bool cmp(point a,point b){if(a.x b.x) return a.y b.y;return a.x b.x;
}bool cmp1(point a,point b){return a.y b.y;
}LL dist(point a ,point b){return (a.x-b.x) * (a.x-b.x) (a.y-b.y) * (a.y-b.y);
}/** 二维空间找最近点对* 返回排序后点位置的pairint,int*/
pairint,int Closest_Pair(int l ,int r){if(l r || l1 r) return make_pair(l,r); //1个点,2个点 直接return;int m Mid(l,r); // (lr)/2pairint,int dl Closest_Pair(l,m);pairint,int dr Closest_Pair(m1,r);LL ldis,rdis; //左部分的最值 右部分的最值LL ans_dis; //左中右三部分最值if(dl.first dl.second) ldis INF; //判重else ldis dist(p[dl.first],p[dl.second]);if(dr.first dr.second) rdis INF;else rdis dist(p[dr.first],p[dr.second]);pairint,int ans ldis rdis ? dl : dr ; //左右两部分的最值点对ans_dis min(ldis,rdis); //左右两部分的最值// 从中向左右两边找在[p[m].x-d,p[m].xd]的平面内所有点// 这以后的复杂度就不太好估计了...// 这段模板是用暴力找的...我只做了一点点优化...但为什么加剪枝时间还多了这我不太理解囧int cnt 0;
// for(int i l; i r; i)
// {
// if((long long)(p[m].x - p[i].x)*(p[m].x - p[i].x) ans_dis)
// tmp[cnt] p[i];
// }for(int i m ; i l ; i--){LL q (p[m].x - p[i].x) * (p[m].x - p[i].x);if(p[i].x p[m].x - q) break;if(q ans_dis){tmp[cnt] p[i];}}for(int i m1 ; i r ; i){LL q (p[m].x - p[i].x) * (p[m].x - p[i].x);if(p[i].x p[m].x q) break;if(q ans_dis){tmp[cnt] p[i];}}//按y方向进行筛选 ,相隔大于d的点可以直接跳过sort(tmp,tmpcnt,cmp1);for(int i 0 ; i cnt ; i){for(int j i1 ; j cnt ; j){if((tmp[i].y - tmp[j].y) * (tmp[i].y - tmp[j].y) ans_dis)break;if(dist(tmp[i],tmp[j]) ans_dis){ans_dis dist(tmp[i],tmp[j]);ans make_pair(tmp[i].id,tmp[j].id);}}}return ans;
}void pre(){t[0].x bx % cx;t[0].y by % cy;t[0].pos 0;for(int i 1 ; i n ; i) {t[i].x (t[i-1].x * ax bx) % cx;t[i].y (t[i-1].y * ay by) % cy;t[i].pos i;}
}
int main()
{//FIN;int T;scanf(%d,T);while(T--){scanf(%d%I64d%I64d%I64d%I64d%I64d%I64d,n,ax,bx,cx,ay,by,cy);pre();LL res 0 ;while(n){for(int i 0 ; i n ; i)p[i] t[i];sort(p,pn,cmp);for(int i 0 ; i n ; i)p[i].id i;pairint,int ans Closest_Pair(0,n-1);int last max(p[ans.first].pos,p[ans.second].pos);res (dist(p[ans.first],p[ans.second]) * (n - last));n last ;}printf(%I64d\n,res);}return 0;
} 转载于:https://www.cnblogs.com/Felix-F/p/3231376.html
