User:Sweepline/UVa 10979.cpp

/*
 *  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[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;
}