Cod sursa(job #1649685)

Utilizator hristacheruxiRuxandra Hristache hristacheruxi Data 11 martie 2016 14:36:50
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1010
struct punct{int x,y;};
punct v[MAX];
punct panta[MAX*MAX];

int cmmdc(int a, int b)
{
    int r;

	if(a<b)
	{
		r=a;
		a=b;
		b=r;
	}

    while(b!=0)
    {
        r=a%b;
        a=b;
        b=r;
    }

    return a;
}

bool cmp(punct a, punct b)
{
    if(a.x<b.x)
        return true;
    else
        if(a.x>b.x)
            return false;
        else
            if(a.y<b.y)
                return true;
            else
                return false;
}

int main(){
    freopen("trapez.in" , "r" , stdin);
    freopen("trapez.out" , "w" , stdout);
    int n,i,j,k,cate,sol,w,xx,yy;

    scanf("%d" , &n);

    for(i=1; i<=n; i++)
        scanf("%d%d" , &v[i].x, &v[i].y);

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

    k=0;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            k++;
            panta[k].x=v[i].x-v[j].x;
            panta[k].y=v[i].y-v[j].y;

            if(panta[k].x!=0 && panta[k].y!=0)
            {
                panta[k].x=panta[k].x/cmmdc(panta[k].x,panta[k].y);
                panta[k].y=panta[k].y/cmmdc(panta[k].x,panta[k].y);
            }
        }

    sort(panta+1, panta+k+1, cmp);

    cate=0; sol=0;
    for(i=1; i<=k; i++)
        if((panta[i].y*panta[i+1].x)==(panta[i+1].y*panta[i].x))
            cate++;
        else
        {
            sol=sol+cate*(cate-1)/2;
            cate=1;
        }
    sol=sol+cate*(cate-1)/2;

    printf("%d\n" , sol);

    return 0;
}