Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <map>
- #include <vector>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- struct point {
- ll x, y;
- };
- ll gcd(ll a, ll b) {
- return b == 0 ? a : gcd(b, a % b);
- }
- ll gcd(ll a, ll b, ll c) {
- if (c == 0 && a == 0)
- return b;
- if (c == 0 && b == 0)
- return a;
- return gcd(gcd(a, b), c);
- }
- istream & operator>>(istream & in, point & p) {
- in >> p.x >> p.y;
- return in;
- }
- bool operator<(point a, point b){
- return a.x < b.x || a.x == b.x && a.y < b.y;
- }
- struct line {
- ll a, b, c;
- line(point p1, point p2) {
- a = p2.y - p1.y;
- b = p1.x - p2.x;
- c = -a * p1.x - b * p1.y;
- ll g = gcd(a, b, c);
- a /= g;
- b /= g;
- c /= g;
- if (a < 0 || a == 0 && b < 0 || a == 0 && b == 0 && c < 0) {
- a = -a;
- b = -b;
- c = -c;
- }
- }
- };
- bool cmp(pair<point, point> a, pair<point, point> b) {
- return a.first < b.first;
- }
- bool operator<(line a, line b) {
- return a.a < b.a || a.a == b.a && a.b < b.b || a.a == b.a && a.b == b.b && a.c < b.c;
- }
- map <line, vector<pair <point, point> > > mp;
- int main()
- {
- point a, b;
- ll n, res = 0;
- cin >> n;
- for (int i = 0; i < n; i++) {
- cin >> a >> b;
- if (b < a)
- swap(a, b);
- mp[line(a, b)].push_back(make_pair(a, b));
- }
- for (map <line, vector<pair <point, point> > >::iterator cur = mp.begin(); cur != mp.end(); cur++) {
- sort((*cur).second.begin(), (*cur).second.end(), cmp);
- for (int i = 0; i < (*cur).second.size(); i++) {
- int l = i, r = (int) (*cur).second.size();
- while (r - l > 1) {
- int m = (l + r) / 2;
- if ((*cur).second[m].first < (*cur).second[i].second)
- l = m;
- else
- r = m;
- }
- res += l - i;
- //cout << (*cur).first.a << " " << (*cur).first.b << " " << (*cur).first.c << endl;
- }
- }
- cout << res;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement