Cod sursa(job #1025430)

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

#include <iostream>
# include <fstream>
using namespace std;
struct fr
{
    int p,q;
};
fr v[1000];
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)
                i++;
            while(a[j].p>a[piv].p)
                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;
}

void quicksort2(int *a,int f,int n)
{
    int p,j,aux,i;
    
    if(f<n)
    {
        p=f;
        i=f;
        j=n;
        
        while(i<j){
            while(a[i]<=a[p]&&i<n)
                i++;
            while(a[j]>a[p])
                j--;
            if(i<j){
                aux=a[i];
                a[i]=a[j];
                a[j]=aux;
            }
        }
        
        aux=a[p];
        a[p]=a[j];
        a[j]=aux;
        quicksort2(a,f,j-1);
        quicksort2(a,j+1,n);
        
    }
}
struct punct
{
    int k,l;
};

int main()
{int n,i,j;
    int h[1000];
    punct o[1000];
    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].p=o[i].l; v[x].q=1;}
                       else if (o[i].k==o[j].k) { v[x].p=o[i].k; v[x].q=1;}
                       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);
    for (i=0;i<x;i++)
        g<<v[i].p<<' '<<v[i].q<<endl;
    h[0]=1;
    n=0;
    for (j=1;j<x;j++)
        if (v[j].p==v[j-1].p && v[j].q==v[j-1].q) h[n]++;
            else {n++; h[n]=1;}
    quicksort2(h,0,n);
    for (i=0;i<n;i++) g<<h[i]<<' ';
    int nr=0;
    for (i=0;i<=n;i++)
        if (h[i]>=2) nr+=(h[i]*(h[i]-1))/2;
    g<<"endl"<<nr;
    f.close();
    g.close();
    return 0;
}