Cod sursa(job #1081249)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 13 ianuarie 2014 13:43:50
Problema Triang Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

double eps=0.001, sinn=0.8660254, coss=0.5;

struct punct{
    double x;
    double y;
};
punct a[1501],p;

bool cmp(punct a,punct b){
    return ((b.x-a.x>eps) || ((fabs(b.x-a.x)<eps) && (b.y-a.y>eps)));
}

int n;

int cautbin(punct b){
    int m;
    int st=1,dr=n;
    while(st<=dr){
        m=(st+dr)/2;
        if((fabs(a[m].x-b.x)<eps) && (fabs(a[m].y-b.y)<eps))
            return m;
        else
            if(cmp(a[m],b))
                st=m+1;
            else dr=m-1;
    }
    return 0;
}
int main()
{
    int i,j;
    ifstream f("triang.in");
    ofstream g("triang.out");
    f>>n;
    for(i=1;i<=n;i++){
        f>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);

    int nr=0;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++){
            p.x=a[i].x+(a[j].x-a[i].x)*coss-(a[j].y-a[i].y)*sinn;
            p.y=a[i].y+(a[j].x-a[i].x)*sinn+(a[j].y-a[i].y)*coss;
            //cout<<cautbin(p)<<" "<<j;
            if(cautbin(p)>j)
                nr++;
            p.x=a[i].x+(a[j].x-a[i].x)*coss+(a[j].y-a[i].y)*sinn;
            p.y=a[i].y-(a[j].x-a[i].x)*sinn+(a[j].y-a[i].y)*coss;
            if(cautbin(p)>j)
                nr++;
            //cout<<"("<<p.x<<" "<<p.y<<")";
           // cout<<" si "<<cautbin(p)<<" "<<j<<endl;
        }
    g<<nr;
    return 0;
}