Cod sursa(job #2558003)

Utilizator darisavuSavu Daria darisavu Data 26 februarie 2020 10:44:05
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct punct
{
    double x,y;
}a[1505];
int n,m,i,j,nr;
double ct1=0.5,ct2=0.8660254038;
double abs(double x, double y)
{
    if(x<y) return y-x;
    else return x-y;
}
int egal(double x,double y)
{
    double dif=abs(x,y);
    if(dif<=0.00001) return 1;
    return 0;
}
int cautbin(double x,double y)
{
    int st=1,dr=n,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(egal(a[mij].x,x))
        {
            if(egal(a[mij].y,y)) return 1;
            else if(a[mij].y<y) st=mij+1;
            else dr=mij-1;
        }
        else if(a[mij].x<x) st=mij+1;
        else dr=mij-1;
    }
    return 0;
}
bool triunghisus(double x,double y, double xx, double yy)
{
    double x3,y3;
    x3=ct1*(xx-x)-ct2*(yy-y)+x;
    y3=ct1*(yy-y)+ct2*(xx-x)+y;
    return cautbin(x3,y3);
}
bool triunghijos(double x,double y, double xx, double yy)
{
    double x3,y3;
    x3=ct1*(xx-x)+ct2*(yy-y)+x;
    y3=ct1*(yy-y)-ct2*(xx-x)+y;
    return cautbin(x3,y3);
}
int compar(punct a, punct b)
{
return (a.x<b.x||(egal(a.x,b.x)&&a.y<b.y));
}
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,compar);
    for(i=1;i<=n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
           if(triunghisus(a[i].x,a[i].y,a[j].x,a[j].y)) nr++;
           if(triunghijos(a[i].x,a[i].y,a[j].x,a[j].y)) nr++;
        }
    }
    g<<nr/3;
    return 0;
}