Cod sursa(job #874734)

Utilizator DEYDEY2Tudorica Andrei DEYDEY2 Data 9 februarie 2013 11:25:00
Problema Trapez Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define PI 3.141592
using namespace std;
typedef struct punct{int x,y;} PUNCT;
typedef struct segm{PUNCT P1, P2;double unghi;} SEGM;
ifstream fi("trapez.in");
ofstream fo("trapez.out");
int n,i,j;
PUNCT P[1001];
int nrs;
SEGM S[500001];
int k;
int rez;
SEGM c;

int cmp1(PUNCT A,PUNCT B)
{
    if (A.x<B.x)
        return 1;
    if (A.x==B.x && A.y<B.y)
        return 1;
    return 0;
}

double panta (PUNCT A, PUNCT B)
{
	if (A.x==B.x)
		return PI/2.0;
    return atan(((double)B.y-A.y)/((double)B.x-A.x));
}

int cmp(SEGM s1, SEGM s2)
{
	if (s1.unghi<=s2.unghi)
		return 1;
	return 0;
}

int f(SEGM s1, SEGM s2)
{
    if (s1.P1.x==s1.P2.x)
        if (s2.P1.x==s2.P2.x)
            return 1;
        else
            return 0;
    if (s2.P1.x==s2.P2.x)
        return 0;
    if ((s1.P2.y-s1.P1.y)*(s2.P2.x-s2.P1.x)==(s2.P2.y-s2.P1.y)*(s1.P2.x-s1.P1.x))
        return 1;
    return 0;
}

int main()
{
	fi>>n;
    for (i=1;i<=n;i++)
        fi>>P[i].x>>P[i].y;
    // se sorteaza punctele
    sort(P+1,P+n+1,cmp1);
    // se formeaza segmentele
    nrs=0;
    for (i=1;i<=n-1;i++)
        for (j=i+1;j<=n;j++)
        {
            nrs++;
            S[nrs].P1=P[i];
            S[nrs].P2=P[j];
			S[nrs].unghi=panta(P[i],P[j]);
        }
    // se ordoneaza segmentele, crescator dupa panta, de fapt dupa unghi
    sort(S+1,S+nrs+1,cmp);
    c=S[1];
    k=1;
    rez=0;
    for (i=2;i<=nrs;i++)
        if (f(c,S[i]))
            k++;
        else
        {
            rez=rez+k*(k-1)/2;
            k=1;
            c=S[i];
        }
    rez=rez+k*(k-1)/2;
	fo<<rez<<'\n';
	fi.close();
	fo.close();
	return 0;
}