Cod sursa(job #1310227)

Utilizator cojocarugabiReality cojocarugabi Data 6 ianuarie 2015 16:43:16
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
# include <bits/stdc++.h>
# define x first
# define y second
using namespace std;
ifstream fi("patrate3.in");
ofstream fo("patrate3.out");
vector < double > y[1005];
pair < double , double > v[1005];
double x[1005];
bool binar(double d,double e,int p,int u)
{
    int a = 1,b = u,bst=1,bs=0;
    while (a < b) if (x[(a+b)>>1] < d) bst = (a+b)>>1,a=(a+b)>>1,++a;else b=(a+b)>>1;
    if (fabs(d - x[bst]) > 0.0001) return 0;
    a = 0,b = y[bst].size()-1;
    while (a < b) if (y[bst][(a+b>>1)] < e) bs = (a+b)>>1,a=(a+b)>>1,++a;else b=(a+b)>>1;
    if (fabs(e - y[bst][bs]) > 0.0001) return 0;
    return 1;
}
int main(void)
{
    int k = 0;
    int n;
    fi>>n;
    for (int i=1;i<=n;++i) fi>>v[i].x>>v[i].y;
    sort(v+1,v+1+n);
    for (int i=1,j;i<=n;i=j)
    {
        ++k;
        x[k] = v[i].x;
        for (j = i;v[j].x == v[i].x && j<=n;++j) y[k].push_back(v[j].y);
    }
    n=k;
    int ans=0;
    /*for (int i=1;i<=k;++i)
    {
        cout << x[i] << ' ';
        for (int j=0;j<y[i].size();++j) cout << y[i][j] << ' ';
        cout << '\n';
    }*/
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
        {
            double x2,y2,x3,y3;
            double mx = (v[i].x + v[j].x)/2.0;
            double my = (v[i].y + v[j].y)/2.0;
            double dx = abs(mx - v[i].x);
            double dy = abs(my - v[i].y);
            if (v[i].y < v[j].y) x2 = mx + dy,y2 = my - dx,x3 = mx - dy,y3 = my + dx;
            else                 x2 = mx - dy,y2 = my - dx,x3 = mx + dy,y3 = my + dx;
       //     cout << v[i].x << ' ' << v[i].y << ' ' << v[j].x << ' ' << v[j].y << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << '\n';
            bool ok1 = 0,ok2 = 0;
            for (int d = 1;d<=n;++d) ok1 |= (x2 == v[d].x && y2 == v[d].y),ok2 |= (x3 == v[d].x && y3 == v[d].y);
            ans += (ok1 && ok2);
        }
     return fo << ans << '\n',0;
}