The Deathly Hallows throws Time Limit Exceeded after refactoring it

[ChrisVilches]

My Accepted solution is stored in URI (submissions view), and also here below. I don't know what changed. The safer approach is to just refactor it again. Current commit (as of now) throws TLE.

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

double EPS = 1e-12;

struct Point {
  double x, y;
  Point(double x, double y) : x(x), y(y) {}
  Point() {}
  Point operator+(const Point& p) { return Point(x + p.x, y + p.y); }
  Point operator-(const Point& p) const { return Point(x - p.x, y - p.y); }
  Point scale(double f) { return Point(x * f, y * f); }
  Point to(const Point& p) const { return p - *this; }
  double operator*(const Point& p) { return x * p.x + y * p.y; }
  double dist(const Point& p) {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
  }
};

struct Segment {
  Point p, q;
  Segment(Point p, Point q) : p(p), q(q) {}
  Segment() {}

  Segment scale(double f) { return Segment(p, p + (q - p).scale(f)); }

  double dist2(Point p, Point q) { return q.to(p) * q.to(p); }

  Point project_point_segment(Segment s, Point c) {
    Point p = s.p;
    Point q = s.q;
    double r = p.to(q) * p.to(q);
    if (fabs(r) < EPS) return p;
    r = (p.to(c) * p.to(q)) / r;
    if (r < 0) return p;
    if (r > 1) return q;
    return p + p.to(q).scale(r);
  }

  double distance_point_segment(Segment s, Point p) {
    return sqrt(dist2(p, project_point_segment(s, p)));
  }

  double segdist(Segment& s, double f) {
    Segment s1 = scale(f);
    return distance_point_segment(s, s1.q);
  }

  double distance(Segment& s) {
    double left = 0L;
    double right = 1L;
    while (fabs(left - right) > 0.0000001L) {
      double third = (right - left) / 3L;
      double third1 = left + third;
      double third2 = right - third;
      if (segdist(s, third1) > segdist(s, third2)) {
        left = third1;
      } else {
        right = third2;
      }
    }
    return segdist(s, left);
  }
};

int N;

struct DisjointSets {
  vector<int> parent, rnk;

  DisjointSets(int n) {
    for (int i = 0; i <= n; i++) {
      rnk.push_back(0);
      parent.push_back(i);
    }
  }

  int find(int u) {
    if (u != parent[u]) parent[u] = find(parent[u]);
    return parent[u];
  }

  void merge(int x, int y) {
    x = find(x), y = find(y);
    if (rnk[x] > rnk[y])
      parent[y] = x;
    else
      parent[x] = y;

    if (rnk[x] == rnk[y]) rnk[y]++;
  }
};

struct Graph {
  int V;
  vector<pair<double, pii>> edges;

  Graph(int V) : V(V) {}

  void add_edge(int u, int v, double w) { edges.push_back({w, {u, v}}); }

  double kruskal_mst() {
    double mst_wt = 0;
    sort(edges.begin(), edges.end());

    DisjointSets ds(V);

    vector<pair<double, pii>>::iterator it;
    for (it = edges.begin(); it != edges.end(); it++) {
      int u = it->second.first;
      int v = it->second.second;

      int set_u = ds.find(u);
      int set_v = ds.find(v);

      if (set_u != set_v) {
        mst_wt += it->first;
        ds.merge(set_u, set_v);
      }
    }

    return mst_wt;
  }
};

int round_up(double n) {
  if (n < 1) return 0;
  if (fabs(floor(n) - n) <= 0.00001) return floor(n);
  return ceil(n);
}

void solve() {
  vector<Segment> segments;

  for (int i = 0; i < N; i++) {
    Segment s;
    scanf("%lf %lf %lf %lf", &s.p.x, &s.p.y, &s.q.x, &s.q.y);
    segments.push_back(s);
  }

  Graph g(segments.size());

  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++)
      g.add_edge(i, j, segments[i].distance(segments[j]));

  printf("%d\n", round_up(g.kruskal_mst()));
}

int main() {
  while (scanf("%d", &N) == 1) solve();
}

[ChrisVilches]

Fixed, and now segment to segment distance is O(1)