hdu 4631 (최근 점 맞 춤, 용기)
1888 단어 HDU
제목:
평면 을 드 리 겠 습 니 다. 매번 점 을 추가 할 때마다 포인트 > = 2 시 에 가장 가 까 운 점 대 거리의 제곱 을 구하 고 마지막 으로 모든 제곱 합 을 출력 합 니 다.
a, b, c x [0] = 0 을 드 립 니 다.x[i]=(x[i-1]*a+b)%c
만약 에 일반적인 방법 에 따라 매번 에 분 치 법 을 실시 하여 가장 가 까 운 점 대 를 구한다 면 TLE 는 용 기 를 이용 하여 매번 x 를 작은 것 에서 큰 것 으로 정렬 하고 점 p 를 하나 도 넣 지 않 고 p 보다 큰 첫 번 째 수 를 찾 은 다음 에 이 수 를 양쪽 에서 찾 으 면 x * x 가 ans 보다 크 면 튀 어 나 올 수 있다.마지막 으로 합치 면 OK.
#include"stdio.h"
#include"string.h"
#include"algorithm"
#include"set"
#define N 500005
typedef __int64 LL;
using namespace std;
struct node
{
LL x,y;
bool operator<(const node &a)const
{
return x<a.x;
}
};
LL x[N],y[N],n;
void fun(LL n,LL x[])
{
LL a,b,c;
scanf("%I64d%I64d%I64d",&a,&b,&c);
int i=0;
x[i]=0;
for(i=1;i<=n;i++)
x[i]=(x[i-1]*a+b)%c;
}
LL min(LL a,LL b)
{
return a<b?a:b;
}
void find()
{
LL i;
LL ans;
LL sum;
LL m1,m2;
scanf("%I64d",&n);
fun(n,x);
fun(n,y);
ans=(LL)1<<60;
sum=0;
multiset<node>M;
for(i=1;i<=n;i++)
{
node p;
p.x=x[i];
p.y=y[i];
if(i>1)
{
multiset<node>::iterator it=M.lower_bound(p),e;
//M.lower_bound （ ）p
for(e=it;e!=M.end();e++)
{
m1=e->x-p.x;
if(m1*m1>=ans)break;
m2=e->y-p.y;
ans=min(ans,m1*m1+m2*m2);
}
for(e=it;e!=M.begin();)
{
e--;
m1=e->x-p.x;
if(m1*m1>=ans)break;
m2=e->y-p.y;
ans=min(ans,m1*m1+m2*m2);
}
sum+=ans;
}
M.insert(p);
}
printf("%I64d
",sum);
M.clear();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
find();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
