Cod sursa(job #1876453)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 12 februarie 2017 13:21:10
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#define sinus 0.8660254
#define cosinus 0.5
#define nmax 1505
#define eps 0.000001
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");

struct point{double x;double y;} v[nmax];
double x,y,a,b;
int sol,n;

int egal(double a,double b)
{
    double dif=a-b;
    if (dif>=-eps&&dif<=eps)
        return 1;
    return 0;
}
int searching(int start,double a,double b)
{
    int i,sol=start;
    for (i=1<<10;i;i>>=1)
        if (sol+i<=n)
            if (a<v[i].x||(egal(a,v[i].x)==0&&b<v[i].y))
                sol+=i;
    if (egal(a,v[sol].x)&&egal(b,v[sol].y))
        return 1;
    if (sol+1<=n)
        sol++;
    if (egal(a,v[sol].x)&&egal(b,v[sol].y))
        return 1;
    return 0;
}
int main()
{
    int i,j;
    f>>n;
    for (i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    for (i=1;i<n;i++)
        for (j=i+1;j<n;j++) {
            x=v[j].x-v[i].x;
            y=v[j].y-v[j].y;

            a=v[i].x+x*cosinus-y*sinus;
            b=v[i].y+x*sinus+y*cosinus;
            sol+=searching(j+1,a,b);

            a=v[i].x+x*cosinus+y*sinus;
            b=v[i].y-x*sinus+y*sinus;
            sol+=searching(j+1,a,b);
        }
    g<<sol<<'\n';
    return 0;
}