Cod sursa(job #2353275)

Utilizator refugiatBoni Daniel Stefan refugiat Data 24 februarie 2019 09:39:58
Problema Triang Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
#define Nmax 20000
using namespace std;
ifstream si("triang.in");
ofstream so("triang.out");
struct point {
    double x, y;
}arr[Nmax];
int n, nr;
int cmp(point a, point b) {
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

bool bs(double x, double y) {
    int st=0, dr=n-1;
    int m;
    double dx, dy;
    while(st<=dr) {
        m=(st+dr)/2;
        dx=arr[m].x-x;
        dy=arr[m].y-y;
        if(abs(dx)<(double)0.0001) {
            if (abs(dy)<(double)0.0001)
                return true;
            if(dy>(double)0.0001) {
                dr=m-1;
            }
            if(-dy>(double)0.0001) {
                st=m+1;
            }
        }
        if(dx>(double)0.0001) {
            dr=m-1;
        }
        if(-dx>(double)0.0001) {
            st=m+1;
        }
    }
    return false;
}

int main() {
    si>>n;
    for(int i=0; i<n; ++i) {
        si>>arr[i].x>>arr[i].y;
    }
    sort(arr, arr+n, cmp);
    double a, b, c, alpha, cp, xp, yp, kns=sqrt(3)/2, l;
    double pp;
    point m;
    for(int i=0; i<n-1; ++i) {
        for(int j=i+1; j<n; ++j) {
            if(i-j) {
                m.x=(arr[i].x+arr[j].x)/2;
                m.y=(arr[i].y+arr[j].y)/2;
                a=arr[j].y-arr[i].y;
                b=arr[i].x-arr[j].x;
                c=arr[i].y*arr[j].x-arr[i].x*arr[j].y;
                pp=(a*a)+(b*b);
                l=sqrt(pp);
                alpha=pp*kns;
                cp=a*m.y-b*m.x;
                xp=(a*alpha-cp*b-a*c)/pp;
                if(b) {
                    yp=(alpha-c-a*xp)/b;
                }
                else {
                    yp=cp/a;
                }
                if(bs(xp, yp)) {
                    nr++;
                }
                alpha*=-1;
                xp=(a*alpha-cp*b-a*c)/pp;
                if(b) {
                    yp=(alpha-c-a*xp)/b;
                }
                else {
                    yp=cp/a;
                }
                if(bs(xp, yp)) {
                    nr++;
                }
            }
        }
    }
    so<<nr/3;
}