Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define MAX 50005
  3. using namespace std;
  4. int n;
  5. double h[MAX];
  6. struct point {
  7. int x, y;
  8. bool operator<(const point &pt2) const {
  9. return x < pt2.x;
  10. }
  11. };
  12. point pontos[MAX];
  13. double dist(point a, point b) {
  14. return sqrt(pow(a.x - b.x, 2) + pow(a.y-b.y, 2));
  15. }
  16. bool compara(point a, point b) {
  17. return a.x < b.x;
  18. }
  19. map<point, int> indice;
  20. int main() {
  21. scanf("%d", &n);
  22. for (int i = 1; i <= n; i++) scanf("%d %d", &pontos[i].x, &pontos[i].y);
  23. for (int i = 1; i <= n; i++) indice[pontos[i]] = i-1;
  24. sort(pontos+1, pontos+n+1, compara);
  25. h[2] = dist(pontos[1], pontos[2]);
  26. vector<point> ateagora;
  27. ateagora.push_back(pontos[1]);
  28. ateagora.push_back(pontos[2]);
  29. point ansa = pontos[1], ansb = pontos[2];
  30. double ansc=h[2];
  31. for (int i = 3; i <= n; i++) {
  32. point pp; pp.x = pontos[i].x - h[i-1];
  33. h[i] = h[i-1];
  34. vector<point>::iterator it = lower_bound(ateagora.begin(), ateagora.end(), pp, compara);
  35. for (; it != ateagora.end(); it++) {
  36. point ponto = *it;
  37. if (dist(ponto, pontos[i]) < h[i]) {
  38. ansc = h[i] = dist(ponto, pontos[i]);
  39. ansa = ponto;
  40. ansb = pontos[i];
  41. }
  42. }
  43. ateagora.push_back(pontos[i]);
  44. }
  45. int a = min(indice[ansa], indice[ansb]), b = max(indice[ansa], indice[ansb]);
  46. printf("%d %d %.6f\n", a, b, ansc);
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement