Cod sursa(job #589977)

Utilizator Andy_MascaMasca Andrei Andy_Masca Data 14 mai 2011 20:36:09
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream.h>
#include <math.h>
using namespace std;
#define Nmax 501

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

struct punct {long x, y;};

long n,i,j,m,k,nr_trapez;

punct pante[Nmax], puncte[1001], aux;

void quick(long li, long ls);
void poz (long li, long ls, long&k);


int main()
{
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>puncte[i].x>>puncte[i].y;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
        m++;
        pante[m].x=abs(puncte[i].x-puncte[j].x);
        pante[m].y=abs(puncte[i].y-puncte[j].y);
        }
    quick(1,m);
    i=1;
    while(i<=m-1)
    {
    j=i+1;
    while((j<=m)&&(pante[i].y*pante[j].x==pante[j].y*pante[i].x))
                j++;
        long v=j-i;
        fout<<v<<" ";
        if(v>1)
           nr_trapez+=((v)*(v-1)/2);
        i=j;
    }
     fout<< nr_trapez;
 return 0;
}
void quick(long li, long ls)
{
    if(li<ls)
    {
    poz(li,ls,k);
    quick(li,k-1);
    quick(k+1,ls);
    }
}

void poz(long li,long ls,long &k)
{
    int i=li,j=ls,i1=0,j1=-1,c;
    while(i<j)
    {
        if(pante[i].y*pante[j].x>pante[j].y*pante[i].x)
        {
        aux=pante[j];
        pante[j]=pante[i];
        pante[i]=aux;
        c=i1;
        i1=-j1;j1=-c;
        }
        i+=i1;
        j+=j1;
    }
    k=i;
}