Cod sursa(job #1081192)

Utilizator impulseBagu Alexandru impulse Data 13 ianuarie 2014 12:36:28
Problema Trapez Scor 20
Compilator c Status done
Runda Arhiva de probleme Marime 2.38 kb
//
//  main.c
//  trapez
//
//  Created by Alexandru Bâgu on 1/13/14.
//  Copyright (c) 2014 Alexandru Bâgu. All rights reserved.
//

#include <stdio.h>
typedef struct {
    int x, y;
    long long int h;
} coord;
typedef struct {
    coord a, b;
    float m; //m = (Yb - Ya) / (Xb - Xa)
} line;
float slope(coord a, coord b)
{
    if(b.y - a.y == 0) return 0;
    return (float)(b.x - a.x) / (float)(b.y - a.y);
}
int slopematch(line a, line b)
{
    line A; A.a = a.a; A.b = b.a;
    line B; B.a = a.b; B.b = b.b;
    if(slope(A.a, A.b) == slope(B.a, B.b))
        return 1;
    return 0;
}
int swap(line* a, line* b)
{
    line aux = *a;
    *a = *b;
    *b = aux;
    return 0;
}
int qsort(line* L, int a, int b)
{
    if(a < b)
    {
        int s = a, d = b, w = 1;
        while(s != d)
        {
            if(L[s].m <= L[d].m)
            {
                if(w) s++;
                else d--;
            }
            else
            {
                swap(L + s, L + d);
                w ^= 1;
            }
        }
        qsort(L, a, s - 1);
        qsort(L, s + 1, b);
    }
    return 0;
}
int valid(line a, line b)
{
    if(a.m == b.m)
    {
        if(a.a.h == a.b.h ||
           a.a.h == b.a.h ||
           a.a.h == b.b.h ||
           a.b.h == b.a.h ||
           a.b.h == b.b.h ||
           b.a.h == b.b.h)
            return 0;
        return 1;
    }
    return 0;
}
int main(int argc, const char * argv[])
{
    freopen("trapez.in", "r", stdin);
    freopen("trapez.out", "w", stdout);
    int n;
    scanf("%d", &n);
    coord* C = (coord*)malloc(n * sizeof(coord));
    int i, j, tx = 0;
    for(i = 0; i < n; i++)
    {
        scanf("%d %d", &C[i].x, &C[i].y);
        C[i].h = (long long int)C[i].x;
        C[i].h <<= 32;
        C[i].h += C[i].y;
    }
    line* L = (line*)malloc(n * n * sizeof(line));
    for(i = 0; i < n; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            L[tx].a = C[i];
            L[tx].b = C[j];
            L[tx].m = slope(C[i], C[j]);
            tx++;
        }
    }
    qsort(L, 0, tx - 1);
    int tr = 0;
    for(i = 0; i < tx; i++)
        for(j = i + 1; j < tx; j++)
            if(valid(L[i], L[j]))
            //{ printf("%d.%d %d.%d -- %d.%d %d.%d\n", L[i].a.x, L[i].a.y, L[i].b.x, L[i].b.y, L[j].a.x, L[j].a.y, L[j].b.x, L[j].b.y);
                tr += 1 + slopematch(L[i], L[j]);
            //}
    printf("%d", tr);
    return 0;
}