Cod sursa(job #969916)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 5 iulie 2013 17:26:47
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
// cu formula rotatiei in complex:
//Dacă M3(z3) se obţine printr-o rotaţie cu
//centrul în M2(z2) şi unghi α ∈[0,2π ), a punctului M1(z1), atunci :
//z3=z2+(z2-z1)ε, unde ε = cosα + i sinα , dacă rotaţia se efectuează în sens
//trigonometric sau ε = cos(2π −α )+ i sin(2π −α ), dacă rotaţia se efectuează în
//sens invers trigonometric.
#include <iostream>
#include <algorithm>
#include <cmath>
#define ERR 0.0000001
#include <fstream>
using namespace std;
int n,sol;
struct punct {double x,y;};
struct complex {double r,i;};
punct a[1005];
inline int cmp (punct A, punct B)
{
    if (fabs(A.x-B.x)<ERR)
        return (A.y<B.y);
    return (A.x<B.x);
}
inline void atribuire1 (complex &z, punct p)
{
    z.r=p.x;
    z.i=p.y;
}
inline void atribuire2 (punct &p, complex z)
{
    p.x=z.r;
    p.y=z.i;
}
inline complex suma (complex z1, complex z2)
{
    complex x;
    x.r=z1.r+z2.r;
    x.i=z1.i+z2.i;
    return x;
}
inline complex scadere (complex z1, complex z2)
{
    z2.r=-z2.r;
    z2.i=-z2.i;
    return suma (z1,z2);
}
inline complex inmultire (complex z1, complex z2)
{
    complex rez;
    rez.r=z1.r*z2.r-z1.i*z2.i;
    rez.i=z1.r*z2.i+z1.i*z2.r;
    return rez;
}
void rotatie (complex &z3, complex z2, complex z1)
{
    complex e;
    e.r=0;
    e.i=1;
    z3=suma (z2,inmultire(scadere(z2,z1),e));
}
int cauta (punct p)
{
    int st,dr, mij;
    st=1;
    dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if ( fabs(a[mij].x-p.x)<ERR && fabs(a[mij].y-p.y)<ERR)
            return 1;
        if (cmp(a[mij],p))
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}
int main()
{
    fstream f,g;
    f.open("patrate3.in",ios::in);
    g.open("patrate3.out",ios::out);
    f>>n;
    int i,j;
    for (i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+1+n,cmp);
    complex z1,z2,z3,z4,zm;
    punct A,B;
    for (i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            atribuire1(z1,a[i]);
            atribuire1(z2,a[j]);
            zm.r=(z1.r+z2.r)/2;
            zm.i=(z1.i+z2.i)/2;
            rotatie (z3,zm,z1);
            rotatie (z4,zm,z2);
            atribuire2(A,z3);
            atribuire2(B,z4);
            if (cauta(A) && cauta(B))
                sol++;
        }
    g<<sol/2;
}