Cod sursa(job #846844)

Utilizator siminescuPaval Cristi Onisim siminescu Data 2 ianuarie 2013 21:09:15
Problema Triang Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<fstream>
#include<math.h>
#include<iomanip>
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct structura{double x,y;};
structura p[1502];
int n;
void citire()
{
    f>>n;int i;
    for(i=0;i<n;i++) f>>p[i].x>>p[i].y;
}
void sortare()
{
    int i,j;
    double aux;
    for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
        {
            if(p[i].x>p[j].x||(p[i].x==p[j].x&&p[i].y>p[j].y))
            {
                aux=p[i].x;
                p[i].x=p[j].x;
                p[j].x=aux;
                aux=p[i].y;
                p[i].y=p[j].y;
                p[j].y=aux;
            }
        }
}
double absolut(double a)
{
    if(a<0) return -a;
    return a;
}
int search(double a,double b,int st)
{
    int dr=n-1,mij;
    do{
        mij=(st+dr)/2;
        if(absolut(p[mij].x-a)<0.001&&absolut(p[mij].y-b)<0.001)
            return 1;
        if(p[mij].x>a||(absolut(p[mij].x-a)<0.001&&p[mij].y>b)) dr=mij;
        else st=mij+1;
    }while(st<dr);
        return 0;
}
int main()
{
    citire();sortare();
    double t,q,a,b,rad3=1.7320508075688772935;int i,j,nr=0;
    for(i=0;i<n-2;i++)
        for(j=1+i;j<n-1;j++)
        {
            a=p[i].x-p[j].x;b=p[i].y-p[j].y;
            t=(a-b*rad3)/2;q=(a*rad3+b)/2;
            nr+=search(t+p[j].x,q+p[j].y,j+1);
            t=(a+b*rad3)/2;q=(b-a*rad3)/2;
            nr+=search(t+p[j].x,q+p[j].y,j+1);
	    t=(a-b*rad3)/2;q=(b-a*rad3)/2;
            nr+=search(t+p[j].x,q+p[j].y,j+1);
	    t=(a+b*rad3)/2;q=(b+a*rad3)/2;
            nr+=search(t+p[j].x,q+p[j].y,j+1);
        }
    g<<nr;
}