Cod sursa(job #1809974)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 19 noiembrie 2016 14:33:58
Problema Patrate 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#define N 1010
#define POW 10000
#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;
}

int main(){
    int i,j;
    int px,py;
    long long d;
    int nrsol=0;
    point a ,b ,x, y;

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



    READ();

    for(i=0;i<n;i++){
        for(j=i+1;j<n;j++){
            d = dist( pt[i] ,pt[j] );
            d = abs(d);
            ht[ d % MOD ].push_back(make_pair(d , i*POW +j ) );
        }
    }

    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/2);

    return 0;
}