2316.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2316 on 2006-08-15 at 15:13:17 */ 
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 102400;

class Segment {
public:
	int x1, y1, x2, y2;
	int64 dx, dy, ddx, ddy;
	void make();
	int left() const { return dx == 0 ? y1 : x1; }
	int right() const { return dx == 0 ? y2 : x2; }
	bool operator <(const Segment&) const;
	bool operator ==(const Segment&) const;
};
void Segment::make() {
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	if(x1 > x2 || (x1 == x2 && y1 > y2)) { swap(x1, x2); swap(y1, y2); }
	dx = x2-x1; dy = y2-y1; ddy = (int64)x2*y1-(int64)x1*y2;
	if(dx == 0) ddy = abs(ddy);
}
bool Segment::operator <(const Segment& s) const {
	int64 k = dx*s.dy-dy*s.dx, d = dx*s.ddy-ddy*s.dx;
	if(k != 0) return k < 0;
	else if(dx == 0 && x1 != s.x1) return x1 < s.x1;
	else if(d != 0) return d < 0;
	else if(dx == 0) return y1 < s.y1;
	else return x1 < s.x1;
}
bool Segment::operator ==(const Segment& s) const {
	if(dx*s.dy != dy*s.dx) return false;
	else if(dx == 0) return x1 == s.x1;
	else return dx*s.ddy == ddy*s.dx;
}

Segment s[N];

int main()
{
	int T, n;

	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		scanf("%d", &n);
		for(int i = 0; i < n; i++) s[i].make();
		sort(s, s+n);
		int64 pn = 0;
		for(int i = 0, j = 0; i < n; i = j) {
			priority_queue< int, vector<int>, greater<int> > Q;
			for(; j < n && s[i] == s[j]; j++) {
				while(!Q.empty() && s[j].left() >= Q.top()) Q.pop();
				pn += Q.size(); Q.push(s[j].right());
			}
		}
		printf("Scenario #%d:\n%lld\n\n", t, pn);
	}
	
	return 0;
}