Cod sursa(job #1017186)

Utilizator jul123Iulia Duta jul123 Data 27 octombrie 2013 14:13:05
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
long long pa1[500000], pa2[500000];

int cmp(int i, int j)
{
    if (pa1[i]*pa2[j]>pa1[j]*pa2[i])
        return 1;
    if(pa1[i]*pa2[j]==pa1[j]*pa2[i])
        return 0;
    return -1;
}
int pivot(int left, int right)
{
    int p1,p2,p3,p,mini,maxi;
    p1=left + rand() % (right-left+1);
    p2=left + rand() % (right-left+1);
    p3=left + rand() % (right-left+1);
    if(cmp(p1, p2) <=0 && cmp(p1, p3)<=0)
        mini=p1;
    if(cmp(p2, p1) <=0 && cmp(p2,p3)<=0)
        mini=p2;
    if(cmp(p3, p1) <=0 && cmp(p3,p2) <=0)
        mini=p3;
    if(cmp(p1,p2)>=0 && cmp(p1,p3)>=0)
        maxi=p1;
    if(cmp(p2,p1)>=0 && cmp(p2,p3)>=0)
        maxi=p2;
    if(cmp(p3,p1)>=0 &&cmp(p3,p2)>=0)
        maxi=p3;
    p=p1+p2+p3-maxi-mini;
    return p;

}
void quicksort(int left, int right)
{
    int i=left, j=right, tmp, piv;
    piv=pivot(left,right);
    while(i<=j)
    {
        while(cmp(i,piv)<0)
            i++;
        while(cmp(j,piv)>0)
            j--;
        if(i<=j)
        {
            tmp=pa1[i];
            pa1[i]=pa1[j];
            pa1[j]=tmp;
            tmp=pa2[i];
            pa2[i]=pa2[j];
            pa2[j]=tmp;
            i++;
            j--;
        }
    }

    if(left<j)
        quicksort(left,j);
    if(i<right)
        quicksort(i,right);

}
int main()
{
ifstream f("trapez.in");
ofstream g("trapez.out");
int n, i, k, s, nr, j,aa,u, v, bb, d;
long long x[1000], y[1000];
f>>n;
for(i=0;i<n;i++)
    f>>x[i]>>y[i];
k=0;
for(i=0;i<n-1;i++)
    for(j=i+1;j<n;j++){
        pa1[k]=(x[j]-x[i]);
        pa2[k]=(y[j]-y[i]);

        k++;
    }
quicksort(0,k-1);
s=0;
nr=1;


for(i=1;i<k;i++)
{
    if(cmp(i,i-1)==0){
        nr++;}
    else
    {

        s+=nr*(nr-1)/2;
        nr=1;
    }
}
s+=nr*(nr-1)/2;
g<<s;
g.close();
return 0;

}