Cod sursa(job #1604398)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 18 februarie 2016 11:16:24
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream f("trapez.in");
ofstream g("trapez.out");

int n, i, j;
struct punct
{
    int x, y;
}a[1001];
struct dreapta
{
    double alpha;
    int x, y;
}b[800001];
int nr, cnt;

bool cmp(punct a, punct b)
{
    return (a.y == b.y ? a.x < b.x : a.y < b.y);
}

bool cmp2(dreapta a, dreapta b)
{
    if (a.alpha == b.alpha)
        if (a.x == b.x)
            return a.y < b.y;
        else
            return a.x < b.x;
    return a.alpha < b.alpha;
}

int main()
{
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i].x >> a[i].y;

    sort(a+1, a+n+1, cmp);

    for (i = 1; i < n; i++)
        for (j = i+1; j <= n; j++)
        {
            nr++;
            b[nr].x = a[i].x, b[nr].y = a[i].y;
            //b[nr].alpha =
            int dx = a[j].x-a[i].x, dy = a[j].y-a[i].y;
            double dist = sqrt(dx*dx+dy*dy), si = dx/dist, co = dy/dist;
            if (si >= 0 && co >= 0)
                b[nr].alpha = asin(si);
            else if (si < 0 && co >= 0)
                b[nr].alpha = 2*M_PI-asin(-si);
            else if (si >= 0 && co < 0)
                b[nr].alpha = M_PI-acos(-co);
            else if (si < 0 && co < 0)
                b[nr].alpha = M_PI+asin(-si);
        }

    sort(b+1, b+nr+1, cmp2);
    for (i = 1; i < nr; i++)
    {
        //g << b[i].alpha << " ";
        for (j = i+1; b[i].alpha == b[j].alpha && j <= nr; j++)
            if (!(b[i].x == b[j].x && b[i].y == b[j].y))
                cnt++;
    }
    g << cnt;
    return 0;
}