Cod sursa(job #2789637)

Utilizator mateitudordmDumitru Matei mateitudordm Data 27 octombrie 2021 19:06:18
Problema Triang Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <bits/stdc++.h>
#define PI 3.14159265
#define sin1 sin(PI / 3)
#define cos1 cos(PI / 3)
#define sin2 sin(-PI / 3)
#define cos2 cos(-PI / 3)
#define eps 0.001

using namespace std;

struct pct
{
    double x, y;
} v[1501];
int n;
bool cmp(pct a, pct b)
{
    if (a.x - b.x < eps && a.x - b.x >= 0)
        return a.y - b.y < 0;
    return a.x - b.x < 0;
}
bool caut(double x, double y)
{
    int st = 0, dr = n - 1, mij, sol = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij].x - x < eps || (v[mij].x - x == eps && v[mij].y - y <= eps))
            st = mij + 1, sol = mij;
        else
            dr = mij - 1;
    }
    return (v[sol].x - x < eps && v[sol].x - x > 0 && v[sol].y - y < eps && v[sol].y - y > 0);
}

int main()
{
    ifstream cin("triang.in");
    ofstream cout("triang.out");
    int i, j, cnt = 0;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> v[i].x >> v[i].y;
    }
    sort(v, v + n, cmp);
    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            double x1, x2, y1, y2, xx, yy;
            x1 = v[i].x, x2 = v[j].x, y1 = v[i].y, y2 = v[j].y;
            y2 -= y1, x2 -= x1;
            xx = x2 * cos1 - y2 * sin1;
            yy = x2 * sin1 + y2 * cos1;
            y1 += yy, x1 += xx;
            if (caut(x1, y1))
                cnt++;
            x1 = v[i].x, x2 = v[j].x, y1 = v[i].y, y2 = v[j].y;
            y2 -= y1, x2 -= x1;
            xx = x2 * cos2 - y2 * sin2;
            yy = x2 * sin2 + y2 * cos2;
            y1 += yy, x1 += xx;
            if (caut(x1, y1))
                cnt++;
        }
    }
    cout << cnt;
}