Pagini recente » Cod sursa (job #103882) | Cod sursa (job #2391646) | Cod sursa (job #1452691) | Cod sursa (job #2587839) | Cod sursa (job #2073237)
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
struct {
int x, y;
} p[1000], m[1000000];
///p: A(x, y)
///m: dif de y/ dif de x => m[].x = dif de y
/// m[].y = dif de x
ifstream fin("trapez.in");
ofstream fout("trapez.out");
int part_Hoare ( int s, int d )
{
int i, j;
i = s-1;
j= d+1;
int randpoz, r1, r2, r3;
int nr = d-s+1;
r1 = rand() % nr + s;
r2 = rand() % nr + s;
r3 = rand() % nr + s;
int minr, maxr;
minr = min ( min(r1, r2), min(r2, r3) );
maxr = max ( max(r1, r2), max(r2, r3) );
randpoz = r1+r2+r3 - minr-maxr;
int pivot_x = m[randpoz].x;
int pivot_y = m[randpoz].y;
while (true){
do
{
++i;
}while( m[i].x * pivot_y < m[i].y * pivot_x );
do
{
--j;
}while( m[j].x * pivot_y > m[j].y * pivot_x);
if( i>=j )
return j;
//swap
int aux_x, aux_y;
aux_x = m[i].x;
aux_y = m[i].y;
m[i].x = m[j].x;
m[i].y = m[j].y;
m[j].x = aux_x;
m[j].y = aux_y;
}
}
void qsort (int i, int j)
{
if(i<j){
int k = part_Hoare( i, j );
qsort(i, k);
qsort(k+1, j);
}
}
/*void sortare(int k)
{
int i, j;
for(i=0; i<k; i++)
for(j=i+1; j<=k; j++)
{
if( (m[i].x * m[j].y) > (m[i].y * m[j].x) )
{
int aux_x, aux_y;
aux_x = m[i].x;
aux_y = m[i].y;
m[i].x = m[j].x;
m[i].y = m[j].y;
m[j].x = aux_x;
m[j].y = aux_y;
}
}
}*/
int main()
{
int n, i, j;
long long nr_part=0, nr_total=0, nr_x0=1;
fin>>n;
for(i=0; i<n; i++)
fin>>p[i].x>>p[i].y;
int k = -1;
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
{
if(p[i].x == p[j].x)
if(nr_x0 == 0)
nr_x0 = 2;
else
nr_x0++;
else
{
++k;
m[k].x = p[j].y - p[i].y;
m[k].y = p[j].x - p[i].x;
}
}
//cout<<"nr_x0: "<<nr_x0<<endl;
/*cout<<"nesortate pantele:"<<endl;
for(i=0; i<=k; i++)
cout<<m[i].x<<" "<<m[i].y<<endl;
cout<<endl;*/
qsort(0, k);
//sortare(k);
/*cout<<"sortate pantele:"<<endl;
for(i=0; i<=k; i++)
cout<<m[i].x<<" "<<m[i].y<<endl;
cout<<endl;*/
if(nr_x0 > 2)
nr_x0 *= nr_x0-1;
else
if(nr_x0 == 2)
nr_x0 = 1;
nr_total += nr_x0;
i=1;
while( i < n )
{
nr_part=0;
while( p[i].x * p[i-1].y == p[i].y * p[i-1].x )
{
nr_part++;
i++;
}
if(nr_part > 2)
{
nr_part = nr_part*(nr_part-1);
nr_total *= nr_part;
}
i++;
}
fout<<nr_total;
return 0;
}