Cod sursa(job #1457409)

Utilizator NistorSergiuNistor Sergiu NistorSergiu Data 3 iulie 2015 12:37:33
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <algorithm>
#define NMAX 1000

using namespace std;

struct Point{int x, y;};
//struct Line{Point a, b;};

Point pts[NMAX + 1];
Point lns[NMAX * NMAX + 1];


int sgn(Point a)
{
    if(a.x < 0 || a.y < 0)
        return -1;
    return 1;
}

bool compSlope2(Point d1, Point d2)
{
    long long left = d1.y, right = d1.x;
    left *= d2.x;
    right *= d2.y;
    if(1ll * d1.x * d2.x > 0)
        return (left < right);
    return (left > right);
}

bool eqSlope2(Point d1, Point d2)
{
    long long left = d1.y, right = d1.x;
    left *= d2.x;
    right *= d2.y;
    //if(sgn(d1) == sgn(d2))
        return (left == right);
    //return (left > right)
}

int main()
{
    int n;
    int i, j;
    int nrl = 0;
    long long result = 0;
    long long spX = 0, spY = 0;
    ifstream f("trapez.in");
    f >> n;
    for(i = 0; i < n; i++)
        f >> pts[i].x >> pts[i].y;
    f.close();
    for(i = 0; i < n; i++)
        for(j = i + 1; j < n; j++)
        {
            if(pts[i].x == pts[j].x)
            {
                spX++;
                continue;
            }
            if(pts[i].y == pts[j].y)
            {
                spY++;
                continue;
            }
            lns[nrl].x = pts[j].x - pts[i].x;
            lns[nrl].y = pts[j].y - pts[i].y;
            if(lns[nrl].x < 0 && lns[nrl].y < 0)
            {
                lns[nrl].x *= -1;
                lns[nrl].y *= -1;
            }

            nrl++;
        }
    sort(lns, lns + nrl, compSlope2);
    //for(i = 0; i < nrl; i++)
    //    for(j = i + 1; j < nrl; j++)
    //        if(!compSlope(lns[i], lns[j]))
    //            swap(lns[i], lns[j]);
    i = 0;
    for(j = 1; j < nrl; j++)
        if(!eqSlope2(lns[j - 1], lns[j]))
        {
            result += (long long)(j - i) * (j - i - 1) / 2;
            i = j;
        }
    result += (long long)(j - i) * (j - i - 1) / 2;
    result += (spX - 1) * spX / 2;
    result += (spY - 1) * spY / 2;
    ofstream g("trapez.out");
    g << result << '\n';
    g.close();
    return 0;
}