Cod sursa(job #2772625)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 1 septembrie 2021 21:23:34
Problema Triang Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

int n,ans=0;
float rad3=sqrt(3),mat[3],aux[3],xx,yy;

ifstream f("triang.in");
ofstream g("triang.out");

struct punct
{
    double x, y;
} v[1501];

bool cmp(punct a,punct b)
{
    if( a.x-b.x > 1e-3 ) return 0;
    if( b.x-a.x > 1e-3 ) return 1;

    if( a.y-b.y > 1e-3 ) return 0;
    if( b.y-a.y > 1e-3 ) return 1;

    return 1;
}

void roteste()
{
    double inverseaza[3][3];
    for(int i=0; i<3; i++) for(int j=0; j<3; j++) inverseaza[i][j]=0;
    inverseaza[0][1]=1.0;
    inverseaza[1][0]=-1.0;
    inverseaza[2][2]=1.0;

    for(int i=0; i<3; i++)
    {
        aux[i]=0;
        for(int j=0; j<3; j++)
            aux[i]+=mat[j]*inverseaza[j][i];
    }

    for(int i=0; i<3; i++)
    {
        mat[i]=aux[i];
    }
}

int egalitate(double a,double b)
{
    if( a - mat[0] > 1e-3 ) return 1;
    if( mat[0] - a > 1e-3 ) return -1;

    if( b - mat[1] > 1e-3 ) return 1;
    if( mat[1] - b > 1e-3 ) return -1;

    return 0;
}

int main()
{
    f>>n;

    for(int i=1; i<=n; i++)
    {
        f>>v[i].x>>v[i].y;
    }

    sort(v+1,v+n+1,cmp);

    for(int i=1; i<=n-1; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            xx=(v[i].x+v[j].x)/2,yy=(v[i].y+v[j].y)/2;
            double coordx=xx+(v[i].x-xx)*rad3,coordy=yy+(v[i].y-yy)*rad3;

            int st,dr,mid;

            mat[0]=coordx-xx;
            mat[1]=coordy-yy;
            mat[2]=1;
            roteste();
            mat[0]+=xx;
            mat[1]+=yy;

            st=1;
            dr=n;

            while( st<=dr )
            {
                mid=(st+dr)/2;
                if( egalitate(v[mid].x,v[mid].y)>0 ) dr=mid-1;
                else if( egalitate(v[mid].x,v[mid].y)<0 ) st=mid+1;
                else
                {
                    ans++;
                    break;
                }
            }

            mat[0]=xx-(mat[0]-xx);
            mat[1]=yy-(mat[1]-yy);

            st=1;
            dr=n;

            while( st<=dr )
            {
                mid=(st+dr)/2;

                if( egalitate(v[mid].x,v[mid].y)>0 ) dr=mid-1;
                else if( egalitate(v[mid].x,v[mid].y)<0 ) st=mid+1;
                else
                {
                    ans++;
                    break;
                }
            }
        }
    }

    g<<ans/3;

    return 0;
}