Cod sursa(job #1810018)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 19 noiembrie 2016 15:22:05
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.26 kb
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define N 1010
#define POW 100000
#define MOD 1293239

using namespace std;

struct point {
    int x,y;
};

point pt[N] ;
int n;

//vector < pair<long long,int> > ht[MOD];
//vector < pair<long long,int> >::iterator it;

void READ(){
    static char ch,sir[20];
    long long a,b;
    int len,i,j;

    scanf("%d",&n);
    scanf("%c",&ch);

    for(i=0;i<n;i++){

        scanf("%s",sir);

        a=b=0;
        len=strlen(sir);

        for(j=0;j<len;j++){
            if( sir[j] >= '0' && sir[j] <= '9' ){
                a = a*10 + sir[j]-'0';
            }
        }
        if(sir[0] == '-'){
            a=-a;
        }


        scanf("%s",sir);

        len=strlen(sir);

        for(j=0;j<len;j++){
            if( sir[j] >= '0' && sir[j] <= '9' ){
                b = b*10 + sir[j]-'0';
            }
        }
        if(sir[0] == '-'){
            b=-b;
        }

     //   printf("%lld %lld\n",a,b);

        pt[i].x = a;
        pt[i].y = b;
    }
}

long long dist(point a , point b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

//
//int sgn( point a, point b, point c){
//    static int val;
//
//    val = ( b.x - a.x ) * ( c.y - a.y ) - ( c.x  - a.x) * ( b.y - a.y );
//
//    if(val == 0){
//        return 2;
//    }else if( val > 0){
//        return 1;
//    }
//    return -1;
//}

bool cmp (point a , point b){
    if( a.x != b.x){
        return a.x < b.x;
    }
    return a.y < b.y;
}

int bnrsch (long long x , long long y){
    int l,r, mid;

    l=0;
    r=n;

    while(l <= r){
        mid = (l + r )/2;

        if( pt[mid].x < x){
            l = mid+1;
        }else if ( pt[mid].x > x ){
            r = mid-1;
        }else {
            if( pt[mid].y < y){
                l = mid+1;
            }else if ( pt[mid].y > y ){
                r = mid-1;
            }else {
                return mid;
            }
        }


    }
    return -1;
}

int main(){
    int i,j;
   // int px,py;
   // long long d;
    int nrsol=0;
   // point a ,b ,x, y;
    long long x0,y0,x1,y1,x2,y2,x3,y3,mijx,mijy,dx,dy;
    int p2,p3;

    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);



    READ();

    sort( pt,pt+n,cmp);

    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(  i == j){
                continue;
            }
//            d = dist( pt[i] ,pt[j] );
//            d = abs(d);
//            ht[ d % MOD ].push_back(make_pair(d , i*POW +j ) );
            x0 = pt [i].x;
            x1 = pt [j].x;
            y0 = pt [i].y;
            y1 = pt [j].y;


            x2 = ( x0 + x1 + y0 - y1 ) / 2;
            y2 = ( y0 + y1 + x1 - x0 ) / 2;

            p2=bnrsch(x2,y2);
            if( p2 == -1){
                continue;
            }

            x3 = ( x0 + x1 + y1 - y0) / 2;
            y3 = ( y0 + y1 + x0 - x1) / 2;

            p3=bnrsch(x3,y3);
            if(  p3 == -1){
                continue;
            }
            nrsol++;
//            printf("%lld %lld   %lld %lld   %lld %lld   %lld %lld\n ",x0,y0,x1,y1,x2,y2,x3,y3);
//            printf(" %d %d %d %d \n\n",i,j,p2,p3);
        }
    }

//    for(i=0;i<n;i++){
//        for(j=i+1;j<n;j++){
//            d= dist( pt[i] ,pt[j] );
//            d = abs(d);
//            for( it = ht[ d%MOD ].begin() ; it!= ht[d%MOD].end() ; it++ ){
//                if( it->first != d){
//                    continue;
//                }
//                px = it->second / POW;
//                py = it->second % POW;
//
//                a=pt[i];
//                b=pt[j];
//                x=pt[px];
//                y=pt[py];
//                if( sgn(a,b,x) + sgn (a,b,y) == 0){
//                    if( sgn(x,y,a) + sgn(x,y,b) == 0){
//                        if ( dist(x,a) == dist (x, b) ){
//                            nrsol++;
//                            //printf("%d %d %d %d\n",i,j,px,py);
//                        }
//                    }
//                }
//            }
//
//        }
//    }

    printf("%d",nrsol/4);

    return 0;
}