Cod sursa(job #2792051)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 31 octombrie 2021 19:39:00
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin  ("triang.in");
ofstream fout ("triang.out");

const double MAX_ERROR = 0.0001;
const double sin60 = 0.8660254;
const double cos60 = 0.5;

int n, sol;
struct punct{
    double x, y;
} v[1505];
inline bool cmp(const punct &a, const punct &b){
    if(a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}
double xx, yy, dx, dy;


double poz_val(double k){
    if(k < 0)
        return -k;
    return k;
}

bool verif(double x, double xx){
    double dif=poz_val(x-xx);

    if(dif <= MAX_ERROR)
        return true;
    return false;
}

bool cb(int st, double tx, double ty){
    int md, dr=n;
    while(st <= dr){
        md=(dr-st)/2+st;

        if(verif(tx, v[md].x) == true && verif(ty, v[md].y) == true)
            return true;

        if(v[md].x < tx || (verif(tx, v[md].x) == true && v[md].y < ty))
            st=md+1;
        else
            dr=md-1;
    }
    return false;
}

int main (){
    fin>>n;
    for(int i=1; i<=n; i++)
        fin>>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++){

            /**
            int m1 = (v[i].x + v[i].y) / 2;
            int m2 = (v[j].x + v[j].y) / 2;
            int mx = (v[i].x - v[j].x) / 2;
            int my = (v[i].y - v[j].y) / 2;
            **/

            ///expr pct 2 in func de pct 1
            dx = v[j].x - v[i].x;
            dy = v[j].y - v[i].y;

            ///v1
            xx=v[i].x + dx * cos60 - dy * sin60;
            yy=v[i].y + dx * sin60 + dy * cos60;
            sol += cb(j+1, xx, yy);

            ///v2
            xx=v[i].x + dx * cos60 + dy * sin60;
            yy=v[i].y - dx * sin60 + dy * cos60;
            sol += cb(j+1, xx, yy);
        }

    fout<<sol;
    return 0;
}