User:Sweepline/UVa 10979.cpp

From Algorithmist
< User:Sweepline
Revision as of 09:57, 13 July 2008 by Uniwalk (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

This is an implementation of UVa 10979 in C++.

/*

*  Solution for problem #10979 'How Many Triangles?'
*
*  O(n^5) algorithm: constructs a graph from segments and
*  counts 3-cliques in it.
*/
  1. include <cstdio>
  2. include <cstring>
  3. include <cmath>
  4. include <vector>
  5. include <algorithm>
  6. define EPS 1e-9

using namespace std;

struct Point { double x, y; Point(double x=0, double y=0) : x(x), y(y) {} };

bool operator <(const Point &a, const Point &b) { return a.x<b.x-EPS || (a.x<b.x+EPS && a.y<b.y-EPS); }

bool operator ==(const Point &a, const Point &b) { return fabs(a.x-b.x)<EPS && fabs(a.y-b.y)<EPS; };

struct Segment { double a, b, c; Point A, B;

Segment(Point p1, Point p2) { A = p1; B = p2; /* ax + by = c is the line joining point A and point B */ c=(a=B.y-A.y)*A.x+(b=A.x-B.x)*A.y; } };

/* Is point r on segment s? */ int onseg(Point r, Segment s) { return fabs(s.a*r.x+s.b*r.y-s.c) < EPS && (s.A.x <? s.B.x) - EPS < r.x && r.x < (s.A.x >? s.B.x) + EPS && (s.A.y <? s.B.y) - EPS < r.y && r.y < (s.A.y >? s.B.y) + EPS; }

/* Determines point of intersection of two line segments. */ int isect(Point &r, Segment s, Segment t) { double d = s.a * t.b - s.b * t.a; if (fabs(d) < EPS) return 0; r = Point((s.c * t.b - s.b * t.c) / d, (s.a * t.c - s.c * t.a) / d); return onseg(r, s) && onseg(r, t); }

/* Determines whether the line segments overlap (i.e. are parallel and share

  at least one point), and if so, replaces s with their union. */

int overlap(Segment &s, Segment t) { if (fabs(s.a * t.b - s.b * t.a) > EPS) return 0; if (onseg(t.A, s) && onseg(t.B, s)) return 1; if (onseg(s.A, t) && onseg(s.B, t)) { s = t; return 1; } if (onseg(s.B, t)) swap(s.A, s.B); if (!onseg(s.A, t)) return 0; if (onseg(t.B, s)) swap(t.A, t.B); if (!onseg(t.A, s)) return 0; s = Segment(s.B, t.B); return 1; }

int main() { vector<Segment> S; vector<Point> V; int adj[128][128], i, j, k, n;

while (scanf("%d", &n) == 1) { S.clear(); while (n-- > 0) { double x1, y1, x2, y2; scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2); S.push_back(Segment(Point(x1,y1), Point(x2,y2))); }

/* First, make sure that no two line segments overlap */ do { k = 0; for (i = 0; i < S.size(); i++) for (j = i+1; j < S.size(); j++) if (overlap(S[i], S[j])) { S.erase(S.begin() + j--); k++; } } while (k);

/* * We'll build a graph from given line segments. * The set of vertices (V) are segments' endpoints and points * of intersections. Edges are parts of given line segments. */

V.clear(); for (i = 0; i < S.size(); i++) { V.push_back(S[i].A); V.push_back(S[i].B); for (j = 0; j < i; j++) { Point r; if (isect(r, S[i], S[j])) V.push_back(r); } } sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end());

/* * Now we'll fill the adjacency matrix. * We'll also count number of triangles, whose all vertices * lie on the same line. */ n = 0; memset(adj, 0, sizeof(adj)); for (i = 0; i < S.size(); i++) { /* Find all points, which lie on i-th segments */ vector<int> P; for (j = 0; j < V.size(); j++) if (onseg(V[j], S[i])) P.push_back(j);

/* * Number of triangles with vertices on this segment * is simply the binomial coeficient (k choose 3), * where k is the total number of points on segment. */ k = P.size(); n -= k*(k-1)*(k-2)/6;

/* Join every pair of points with an edge in the graph. */ for (j = 0; j < P.size(); j++) for (k = 0; k < P.size(); k++) adj[P[j]][P[k]] = 1; }

/* Finally, just find the number of 3-cliques in the graph. */ for (i = 0; i < V.size(); i++) for (j = i+1; j < V.size(); j++) if (adj[i][j]) for (k = j+1; k < V.size(); k++) n += adj[j][k] & adj[k][i];

printf("%d\n", n); }

return 0; }