Cod sursa(job #1017941)

Utilizator jul123Iulia Duta jul123 Data 28 octombrie 2013 17:34:55
Problema Trapez Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<iostream>
#include<fstream>
#include<ctime>
#include<cstdlib>
#include<cmath>
using namespace std;
 float pa[50000];
float pivot(int left, int right)
{
    float p1,p2,p3,p,mini,maxi;
    p1=pa[left + rand() % (right-left+1)];
    p2=pa[left + rand() % (right-left+1)];
    p3=pa[left + rand() % (right-left+1)];
    if(p1<=p2&&p1<=p3)
        mini=p1;
    if(p2<=p1&&p2<=p3)
        mini=p2;
    if(p3<=p1&&p3<=p2)
        mini=p3;
    if(p1>=p2&&p1>=p3)
        maxi=p1;
    if(p2>=p1&&p2>=p3)
        maxi=p2;
    if(p3>=p1&&p3>=p2)
        maxi=p3;
    p=p1+p2+p3-maxi-mini;
    return p;

}
void quicksort(int left, int right)
{
    int i=left, j=right, tmp;
    float piv;
    float tmpd;
    piv=pivot(left,right);
    while(i<=j)
    {
        while(pa[i]<piv)
            i++;
        while(pa[j]>piv)
            j--;
        if(i<=j)
        {
            tmpd=pa[i];
            pa[i]=pa[j];
            pa[j]=tmpd;
            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, nr, j,aa,u, v, bb, d;
long x[1001], y[1001], s;
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++)
       {
        if(y[j]==y[i])
            pa[k]=0;
        else if(x[j]==x[i])
                pa[k]=100;
        else{
        if(x[j]>x[i] && y[j]>y[i])
            pa[k]=atan2(x[j]-x[i], y[j]-y[i]);
        if(x[j]<x[i] && y[j]<y[i])
            pa[k]=atan2(x[i]-x[j], y[i]-y[j]);
        if(x[j]>x[i] && y[j]<y[i])
            pa[k]=atan2(x[j]-x[i], y[j]-y[i]);
        if(x[j]<x[i] && y[j]>y[i])
            pa[k]=atan2(x[i]-x[j], y[i]-y[j]);}
        k++;
       }
quicksort(0, k-1);

s=0;
nr=1;
for(i=1;i<k;i++)
{
    if(pa[i]==pa[i-1]){
        nr++;}
    else
    {

        s+=nr*(nr-1)/2;
        nr=1;
    }
}
s+=nr*(nr-1)/2;
g<<s;
}