Cod sursa(job #350179)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 22 septembrie 2009 22:57:17
Problema Trapez Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

#define maxN 1010
#define x    first
#define y    second

using namespace std;

pair <int, int> panta[maxN * maxN], coord[maxN];
int N, k;

bool cmp ( pair <int, int> a, pair <int, int> b) {
        return 1LL * a.x * b.y < 1LL * b.x * a.y;
}

int main(){
    int k = 0, n, i, j, s = 0, t = 1;
    
    freopen("trapez.in","r",stdin);
    freopen("trapez.out","w",stdout);
    
    scanf("%d", &N);
    
    for (i = 1; i <= N; ++ i)
        scanf("%d%d", &coord[i].x, &coord[i].y);

    for (i = 1; i < N; ++ i)
        for (j = i + 1; j <= N; ++ j){
            ++ k;
            panta[k].x = coord[j].x - coord[i].x;
            panta[k].y = coord[j].y - coord[i].y;
        }

    sort (panta + 1, panta + k + 1, cmp);
    
    t = 1;
    for (i = 1; i < k; ++ i){
        if (1LL * panta[i].x * panta[i + 1].y == 1LL * panta[i].y * panta[i + 1].x)
           ++ t;
        else {
             s += t * (t - 1) / 2;
             t = 1;
        }
    }

    s += t * (t - 1) / 2;

    printf("%d\n", s);
    return 0;
}