Cod sursa(job #1041810)

Utilizator Catalina_BrinzaBrinza Catalina Catalina_Brinza Data 26 noiembrie 2013 10:24:26
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
//
//  main.cpp
//  trapez
//
//  Created by Catalina Brinza on 10/28/13.
//  Copyright (c) 2013 Catalina Brinza. All rights reserved.
//


# include <fstream>
using namespace std;
struct fr
{
    int p,q;
};
fr v[1001];
void quicksort(fr *a,int f,int n)
{
    int piv,j,i;
    fr aux;
    if(f<n)
    {
        piv=f;
        i=f;
        j=n;
        
        while(i<j){
            while (a[i].p<=a[piv].p &&i<n)
            {if (a[i].p==a[piv].p && a[i].q>a[piv].q) break;
                i++;}
            
            while(a[j].p>=a[piv].p && j>f)
            {if (a[j].p==a[piv].p && a[j].q<a[piv].q) break;j--;}
            if(i<j){
                aux=a[i];
                a[i]=a[j];
                a[j]=aux;
            }
        }
        
        aux=a[piv];
        a[piv]=a[j];
        a[j]=aux;
        quicksort(a,f,j-1);
        quicksort(a,j+1,n);
        
    }
}
int cmmdc(int h, int z)
{
    int r;
    while (z!=0)
    {
        r=h%z;
        h=z;
        z=r;
        
    }
    return h;
}
void red(fr x)
{int a=abs(x.p), b=abs(x.q);
    int c=cmmdc(a,b);
    while (cmmdc(a,b)!=1)
    {a=a/c;
        b=b/c;
        c=cmmdc(a,b);
    }
    if (x.p<0) x.p=-a;
    else x.p=a;
    if (x.q<0) x.q=-b;
    else x.q=b;
}


struct punct
{
    int k,l;
};

int main()
{int n,i,j;
    punct o[1001];
    ifstream f("trapez.in");
    ofstream g("trapez.out");
    f>>n;
    for (i=0;i<n;i++)
    f>>o[i].k>>o[i].l;
    int x=0;
    for (i=0;i<n-1;i++)
        for (j=i+1;j<n;j++)
        {if (o[i].l==o[j].l) {v[x].q=o[i].l; v[x].p=0;}
        else if (o[i].k==o[j].k) { v[x].p=o[i].k; v[x].q=0;}
        else{
            v[x].p=o[i].l-o[j].l;
            v[x].q=o[i].k-o[j].k;
            red(v[x]);}
            if (v[x].p<0 && v[x].q<0)
            {
                v[x].p=-v[x].p;
                v[x].q=-v[x].q;
            }
            x++;}

   quicksort(v,0,x-1);

   int  nr=0;
    for (j=1;j<x;j++)
        if (v[j].p==v[j-1].p && v[j].q==v[j-1].q) nr++;
    g<<nr;

    f.close();
    g.close();
    return 0;
}