Ближайшая пара SPOJ logN время неверный ответ

Я пытаюсь решить эту проблему. http://www.spoj.com/problems/CLOPPAIR/
Моя основная идея состоит в том, чтобы разделить координаты на части, где в одной и той же части все точки будут иметь одинаковые x. Сортировать все координаты по x и y.
Когда я проверю, какие точки ближе всего к Ni, я сравню его с более высоким y, тем же x и более низким y и тем же x. Я также попытаюсь найти в предыдущей части координаты х и искать их с помощью двоичного поиска, а также я буду искать следующую часть координаты х.
Но я всегда получаю неправильный ответ. Может кто-нибудь сказать мне, что не так. Код ниже.

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <utility>
#include <map>
#include <vector>
using namespace std;
typedef pair<int,int>par;
typedef long long int ll;
par niz[55000];
map<ll,ll>mapa2;
map<par,ll>mapa;
map<ll,ll>mapa3;
vector<par>V[55000];
ll a,b,c,d,e,f;
double euk=1561561616;
ll toc=0,toc2=0;
ll pos1=1,pos2;
void binary(ll pos,ll end)
{
if(pos<pos1-1)
{

ll tockay=V[pos][end].second;
ll low=0;
ll high=V[pos+1].size();
ll midd=0;
while(low<=high)
{
midd=(low+high)/2;
if(V[pos+1][midd].second>tockay)high=midd-1;
else low=midd+1;
}
if(euk>sqrt((V[pos][end].first-V[pos+1][midd].first)*(V[pos][end].first-V[pos+1][midd].first)+(V[pos][end].second-V[pos+1][midd].second)*(V[pos][end].second-V[pos+1][midd].second)))
{
euk=sqrt((V[pos][end].first-V[pos+1][midd].first)*(V[pos][end].first-V[pos+1][midd].first)+(V[pos][end].second-V[pos+1][midd].second)*(V[pos][end].second-V[pos+1][midd].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos+1][midd].first,V[pos+1][midd].second)];
}
if(midd-1>=0)
{
if(euk>sqrt((V[pos][end].first-V[pos+1][midd-1].first)*(V[pos][end].first-V[pos+1][midd-1].first)+(V[pos][end].second-V[pos+1][midd-1].second)*(V[pos][end].second-V[pos+1][midd-1].second)))
{
euk=sqrt((V[pos][end].first-V[pos+1][midd-1].first)*(V[pos][end].first-V[pos+1][midd-1].first)+(V[pos][end].second-V[pos+1][midd-1].second)*(V[pos][end].second-V[pos+1][midd-1].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos+1][midd-1].first,V[pos+1][midd-1].second)];
}
}
if(midd-2>=0)
{
if(euk>sqrt((V[pos][end].first-V[pos+1][midd-2].first)*(V[pos][end].first-V[pos+1][midd-2].first)+(V[pos][end].second-V[pos+1][midd-2].second)*(V[pos][end].second-V[pos+1][midd-2].second)))
{
euk=sqrt((V[pos][end].first-V[pos+1][midd-2].first)*(V[pos][end].first-V[pos+1][midd-2].first)+(V[pos][end].second-V[pos+1][midd-2].second)*(V[pos][end].second-V[pos+1][midd-2].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos+1][midd-2].first,V[pos+1][midd-2].second)];
}
}
if(midd+1<V[pos+1].size())
{
if(euk>sqrt((V[pos][end].first-V[pos+1][midd+1].first)*(V[pos][end].first-V[pos+1][midd+1].first)+(V[pos][end].second-V[pos+1][midd+1].second)*(V[pos][end].second-V[pos+1][midd+1].second)))
{
euk=sqrt((V[pos][end].first-V[pos+1][midd+1].first)*(V[pos][end].first-V[pos+1][midd+1].first)+(V[pos][end].second-V[pos+1][midd+1].second)*(V[pos][end].second-V[pos+1][midd+1].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos+1][midd+1].first,V[pos+1][midd+1].second)];
}
}
if(midd+2<V[pos+1].size())
{
if(euk>sqrt((V[pos][end].first-V[pos+1][midd+2].first)*(V[pos][end].first-V[pos+1][midd+2].first)+(V[pos][end].second-V[pos+1][midd+2].second)*(V[pos][end].second-V[pos+1][midd+2].second)))
{
euk=sqrt((V[pos][end].first-V[pos+1][midd+2].first)*(V[pos][end].first-V[pos+1][midd+2].first)+(V[pos][end].second-V[pos+1][midd+2].second)*(V[pos][end].second-V[pos+1][midd+2].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos+1][midd+2].first,V[pos+1][midd+2].second)];
}
}
}
//prllf("hhkhj %d\n",pos);
if(pos!=1)
{

ll tockay=V[pos][end].second;
ll low=0;
ll high=V[pos-1].size();
ll midd=0;
while(low<=high)
{
midd=(low+high)/2;
if(V[pos-1][midd].second>tockay)high=midd-1;
else low=midd+1;
}
if(euk>sqrt((V[pos][end].first-V[pos-1][midd].first)*(V[pos][end].first-V[pos-1][midd].first)+(V[pos][end].second-V[pos-1][midd].second)*(V[pos][end].second-V[pos-1][midd].second)))
{
euk=sqrt((V[pos][end].first-V[pos-1][midd].first)*(V[pos][end].first-V[pos-1][midd].first)+(V[pos][end].second-V[pos-1][midd].second)*(V[pos][end].second-V[pos-1][midd].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos-1][midd].first,V[pos-1][midd].second)];
}
if(midd-1>=0)
{
if(euk>sqrt((V[pos][end].first-V[pos-1][midd-1].first)*(V[pos][end].first-V[pos-1][midd-1].first)+(V[pos][end].second-V[pos-1][midd-1].second)*(V[pos][end].second-V[pos-1][midd-1].second)))
{
euk=sqrt((V[pos][end].first-V[pos-1][midd-1].first)*(V[pos][end].first-V[pos-1][midd-1].first)+(V[pos][end].second-V[pos-1][midd-1].second)*(V[pos][end].second-V[pos-1][midd-1].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos-1][midd-1].first,V[pos-1][midd-1].second)];
}
}
if(midd-2>=0)
{
if(euk>sqrt((V[pos][end].first-V[pos-1][midd-2].first)*(V[pos][end].first-V[pos-1][midd-2].first)+(V[pos][end].second-V[pos-1][midd-2].second)*(V[pos][end].second-V[pos-1][midd-2].second)))
{
euk=sqrt((V[pos][end].first-V[pos-1][midd-2].first)*(V[pos][end].first-V[pos-1][midd-2].first)+(V[pos][end].second-V[pos-1][midd-2].second)*(V[pos][end].second-V[pos-1][midd-2].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos-1][midd-2].first,V[pos-1][midd-2].second)];
}
}
if(midd+1<V[pos-1].size())
{
if(euk>sqrt((V[pos][end].first-V[pos-1][midd+1].first)*(V[pos][end].first-V[pos-1][midd+1].first)+(V[pos][end].second-V[pos-1][midd+1].second)*(V[pos][end].second-V[pos-1][midd+1].second)))
{
euk=sqrt((V[pos][end].first-V[pos-1][midd+1].first)*(V[pos][end].first-V[pos-1][midd+1].first)+(V[pos][end].second-V[pos-1][midd+1].second)*(V[pos][end].second-V[pos-1][midd+1].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos-1][midd+1].first,V[pos-1][midd+1].second)];
}
}
if(midd+2<V[pos+1].size())
{
if(euk>sqrt((V[pos][end].first-V[pos-1][midd+2].first)*(V[pos][end].first-V[pos-1][midd+2].first)+(V[pos][end].second-V[pos-1][midd+2].second)*(V[pos][end].second-V[pos-1][midd+2].second)))
{
euk=sqrt((V[pos][end].first-V[pos-1][midd+2].first)*(V[pos][end].first-V[pos-1][midd+2].first)+(V[pos][end].second-V[pos-1][midd+2].second)*(V[pos][end].second-V[pos-1][midd+2].second));
toc=mapa[make_pair(V[pos][end].first,V[pos][end].second)];
toc2=mapa[make_pair(V[pos-1][midd+2].first,V[pos-1][midd+2].second)];
}
}
}
}
int main()
{
scanf("%llu",&a);
for(ll i=0;i<a;++i)
{
scanf("%llu%llu",&b,&c);
niz[i]=make_pair(b,c);
mapa[make_pair(b,c)]=i;
}
sort(niz,niz+a);

for(ll i=0;i<a;++i)
{
if(mapa2[niz[i].first]==0)
{
V[pos1].push_back(make_pair(niz[i].first,niz[i].second));
mapa2[niz[i].first]=pos1;
mapa3[pos1]=niz[i].first;
++pos1;
}
else V[pos1].push_back(make_pair(niz[i].first,niz[i].second));
}
for(ll i=0;i<pos1;++i)
{
for(ll j=0;j<V[i].size();++j)
{
if(j!=0)
{
if(euk>V[i][j].second-V[i][j-1].second)
{
euk=V[i][j].second-V[i][j-1].second;
toc=mapa[make_pair(mapa3[i],V[i][j].second)];
toc2=mapa[make_pair(V[i][j-1].first,V[i][j-1].second)];
}
}
if(j!=V[i].size()-1)
{
//prllf("%d\n",V[i][j+1].second-V[i][j].second);
if(euk>V[i][j+1].second-V[i][j].second)
{
euk=V[i][j+1].second-V[i][j].second;
toc=mapa[make_pair(mapa3[i],V[i][j].second)];
toc2=mapa[make_pair(V[i][j+1].first,V[i][j+1].second)];
}
}
binary(i,j);
}
}
printf("%llu %llu %.6lf\n",min(toc,toc2),max(toc,toc2),euk+ + 1e-9);
}

0

Решение

Я не могу сказать вам, в чем ваша ошибка, но я расскажу вам, как ее найти. Написать решение методом грубой силы для небольшого числа точек очень просто — просто вычислите расстояние между любыми двумя парами и найдите минимальное из этих расстояний. Для маленьких п это решение достаточно хорошее. Теперь сгенерируйте случайные точки (скажем, до 20) с относительно небольшими координатами (скажем, до 100) и сравните ответы вашего решения и грубой силы. Продолжайте делать это, пока ответы вашего решения и грубой силы не будут отличаться. Когда я попробовал этот подход, я обнаружил случаи, когда я действительно ошибался, и в первый момент я не смог найти неправильный тест за 20 секунд, а оказалось, что я исправил свое решение.

Я решил очень похожую проблему около недели назад, и я смог исправить свое решение именно так, как я описал. Кроме того, я сделал это во время соревнований по бегу и считаю, что это правильный подход к проблемам, которые могут иметь множество крайних случаев.

Кстати, классическое решение этой проблемы использует разделяй и властвуй и это подход, который я реализовал.

РЕДАКТИРОВАТЬ: на самом деле после небольшой мысли, я думаю, я могу привести пример, что ваше решение у вас не получится. Ваша логика неверна — это может быть тот случай, когда вам понадобится секунда, чтобы длиться х (или даже дальше). Попробуйте этот набор точек: (1, 1), (2,100), (3,2)

1

Другие решения

Других решений пока нет …