Cod sursa(job #1021610)

Utilizator jul123Iulia Duta jul123 Data 3 noiembrie 2013 23:41:58
Problema Triang Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#define rad3 1.73205081
#include<cstdlib>
#include<ctime>


using namespace std;
typedef struct punct{
double x;
double y;}pct;
pct p[1500];
double eps=10e-3;
pct pivot(int left, int right)
{
    pct p1;
    p1=p[left + rand() % (right-left+1)];
    return p1;

}
int cmp(pct a, pct b)
{
    if(a.x-b.x<eps&&a.x-b.x>-eps)
        {if(a.y-b.y<eps&&a.y-b.y>-eps)
            return 0;
        else
            if(a.y-b.y>eps)
                return 1;
        else return -1;
        }
    if(a.x-b.x>eps)
        return 1;
    return -1;
}
void quicksort(int left, int right)
{
    int i=left, j=right;
    pct tmp, piv;
    piv=pivot(left,right);
    while(i<=j)
    {
        while(p[i].x<piv.x)
            i++;
        while(p[j].x>piv.x)
            j--;
        if(i<=j)
        {
            tmp=p[i];
            p[i]=p[j];
            p[j]=tmp;
            i++;
            j--;
        }
    }
    if(left<j)
        quicksort(left,j);
    if(i<right)
        quicksort(i,right);
}

int caut(pct r, int left, int right)
{
    int m;
    if(left<=right)
    {
        m=(left+right)/2;
        if(cmp(p[m],r)==0)
            return 1;
        else
            if(cmp(p[m],r)<0)
            return caut(r,m+1,right);
            else
                return caut(r,left,m-1);
    }
    else
    return 0;
}
int main()
    {
        int n,i,j;
        double x1, y1;
        ifstream f("triang.in");
        ofstream g("triang.out");
        f>>n;
        pct aux;
        for(i=0;i<n;i++)
            f>>p[i].x>>p[i].y;
        quicksort(0,n-1);
        int nr=0;
        for(i=0;i<n-1;i++)
            for(j=i+1;j<n;j++)
            {
                x1=p[i].x+p[i].y*rad3+p[j].x-p[j].y*rad3;
                y1=-p[i].x*rad3+p[i].y+p[j].y+p[j].x*rad3;
                aux.x=x1/2.0;
                aux.y=y1/2.0;
                if(caut(aux,0,n-1)==1)
                    nr++;
               x1=p[i].x+p[j].x+(p[j].y-p[i].y)*rad3;
                y1=p[i].x*rad3+p[j].y+p[i].y-p[j].x*rad3;
                aux.x=x1/2.0;
                aux.y=y1/2.0;
                if(caut(aux,0,n-1)==1)
                    nr++;
            }
        g<<nr/3;
            }