Cod sursa(job #2609533)

Utilizator DeliaGhergheGherghe Ioana-Delia DeliaGherghe Data 2 mai 2020 20:21:59
Problema Trapez Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;

struct punct{ int x, y; }v[1000],pante[500500];

int cmmdc(int a, int b)
{
    while (b != 0)
    {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int compare(const void * a, const void * b)
{
    punct *A = (punct *)a;
    punct *B = (punct *)b;
    if (A->x != B->x)
        return (A->x - B->x);
    else return (A->y - B->y);
}

int main()
{
    ifstream fin("trapez.in");
    ofstream fout("trapez.out");

    int n, i, j;
    int np = 0;

    fin >> n;
    for (i = 0; i < n; i++)
        fin >> v[i].x >> v[i].y;


    for (i = 0; i < n; i++)
        for (j = i+1; j < n; j++)
        {
            int dx = v[j].x - v[i].x;
            int dy = v[j].y - v[i].y;
            if (dy == 0)
            {
                pante[np].x = dy;
                pante[np].y = dx;
                np++;

            }
            else if (dx == 0)
            {
                pante[np].x = -1;
                pante[np].y = dx;
                np++;
            }
            else
            {
                int c = cmmdc(dx, dy);
                dx /= c;
                dy /= c;
                if (dy < 0)
                {
                    dx = -dx;
                    dy = -dy;
                }
                pante[np].x = dy;
                pante[np].y = dx;
                np++;
            }
        }

    qsort(pante, np, sizeof(punct),compare);

    int rez = 0;

    for (i = 0; i < np; i++)
    {
        int nr = 1;
        if (pante[i].x == 0)
            {while (i + 1 < np && pante[i + 1].x == 0)
                {
                    nr = nr + 1;
                    i = i + 1;
                }
            rez += (nr * (nr - 1)) / 2;}
        else if (pante[i].x < 0)
            {while (i + 1 < np && pante[i + 1].x < 0)
                {nr = nr + 1;
                i = i + 1;}
            rez += (nr * (nr - 1)) / 2;}
        else
            {while (i + 1 < np && pante[i + 1].x == pante[i].x && pante[i+1].y == pante[i].y)
                {nr = nr + 1;
                i = i + 1;}
            rez += (nr * (nr - 1)) /2;}
    }
    fout<<rez;
    fin.close();
    fout.close();
    return 0;
}