NCPC2012 Galactic

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <bitset>
#include <iostream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

struct E {
    int a, b, c;
    E(int A, int B, int C) : a(A), b(B), c(C) {}
};

long long int gcd(long long int a, long long int b) {
    return b ? gcd(b, a % b) : a;
}

struct lineEq {

    long long int a, b, c;

    lineEq(int x, int y, int x0, int y0) {
        b = -(x0 - x);
        a = (y0 - y);
        c = -a*x + -b*y;
        int g = gcd(a, b); g = gcd(g, c);
        a/= g;
        b/= g;
        c/= g;
        if (a < 0) {
            a = -a; b = -b; c = -c;
        }
    }

    bool operator==(const lineEq & l) const {
        return a == l.a && b == l.b && c == l.c;
    }

    bool parallel(const lineEq & l) {
        return (a * l.b == l.a * b);
    }

};

vector<lineEq> vl;
int w, n, ax, ay, bx, by, r = 0;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    scanf("%d%d", &w, &n);
    bool allParallel = 1;
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &ax, &ay, &bx, &by);
        lineEq l = lineEq(ax, ay, bx, by);
        bool f = 1;
        for (int j = 0; j < vl.size(); j++) {
            if (vl[j] == l) {
                f = 0;
                break;
            }
        }
        if (f) {
            vl.push_back(l);
            allParallel &= (vl.size() == 1) || (vl[vl.size() - 2].parallel(l));
        }
    }

    n = vl.size();
    w -= (allParallel && n > 1) ? n + 1 : (n << 1);
    if (w <= 0) {
        printf("0"); return 0;
    }

    int ans = 0;
    if (allParallel) {
        w -= (n + 1);
        if (w <= 0) {
            printf("1"); return 0;
        }
        ans = 1;
    }

    printf("%d", ans + (w/2) + (w % 2) );

    return 0;
}