# User:Sweepline/UVa 10979.cpp

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. */ ``````include <cstdio> include <cstring> include <cmath> include <vector> include <algorithm> 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, 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; } ```