Cod sursa(job #2908088)

Utilizator grecubogdanGrecu Bogdan grecubogdan Data 1 iunie 2022 13:37:52
Problema Parantezare optima de matrici Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("triang.in");
ofstream g("triang.out");
struct punct
{
    double x,y;
} p[1501];
int comp(punct a, punct b)
{
    return(abs(a.x-b.x)<0.001&&a.x<b.y||a.x<b.x);
}
int n,k;
void cbin(double x,double y)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(abs(x-p[mij].x)<0.001 && abs(y-p[mij].y)<0.001)
        {
            k++;
            return;
        }
        if(x-p[mij].x<0.001 || (abs(x-p[mij].x)<0.001 && y-p[mij].y<0.001)) dr=mij-1;
        else st=mij+1;
    }
}
double xx,yy;
int main()
{
    int i,j;
    f>>n;
    for(i=1; i<=n; i++)
        f>>p[i].x>>p[i].y;
    sort(p+1,p+n+1,comp);
    for (i=1; i<=n; i++)
    {
        for(j=i+1; j<=n; j++)
        {
            xx=p[i].x+(p[j].x-p[i].x)/2-sqrt(3)*(p[j].y-p[i].y)/2;
            yy=p[i].y+sqrt(3)*(p[j].x-p[i].x)/2+(p[j].y-p[i].y)/2;
            cbin(xx,yy);
            xx=p[i].x+(p[j].x-p[i].x)/2+sqrt(3)*(p[j].y-p[i].y)/2;
            yy=p[i].y-sqrt(3)*(p[j].x-p[i].x)/2+(p[j].y-p[i].y)/2;
            cbin(xx,yy);
        }
    }
    g<<k/3;
    return 0;
}