Pagini recente » Rating Govoreanu Valentin (govo) | Istoria paginii utilizator/oanaoanaoana | Istoria paginii utilizator/rumorsofmydemise | Cod sursa (job #1744917) | Cod sursa (job #96033)
Cod sursa(job #96033)
#include <fstream>
#define MAX 1000001
#define eps 0.001
using namespace std;
struct Punct {
long x;
long y;
} a[MAX], p[MAX];
int c[MAX];
long n, nrtrap, k, y, nr;
void Read();
void Segm();
void Quick(int st, int dr);
ofstream fout ("trapez.out");
int main()
{
nrtrap = 0;
y = 0;
Read();
Segm();
Quick(1,k);
for ( int i = 1; i <= k; i++ )
{
nr = 1;
if ( c[i] != 1 )
{
if ( ((double)p[i].y/(double)p[i].x) == ((double)p[i+1].y/(double)p[i+1].x) )
{
int l = i;
do
{
l++;
nr++;
} while(((double)p[l].y/(double)p[l].x) == ((double)p[l + 1].y/(double)p[l+1].x));
i = l;
nrtrap += ((nr* (nr-1)) / 2);
}
}
else
{
int u = i;
do
{
u++;
nr++;
} while ( c[u] == 1 );
nr--;
if ( nr >= 2 ) nrtrap += ((nr* (nr-1)) / 2);
}
}
fout << nrtrap;
fout.close();
return 0;
}
void Read()
{
ifstream fin ("trapez.in");
fin >> n;
for ( int i = 1; i <= n; i++ )
fin >> a[i].x >> a[i].y;
fin.close();
}
void Segm()
{
k = 0;
for ( int i = 1; i < n; i++ )
{
for ( int j = i + 1; j <= n; j++ )
{
k++;
p[k].y = a[j].y - a[i].y;
c[k] = 0;
if ( a[j].x - a[i].x == 0 )
{
c[k] = 1;
p[k].x = 0;
}
else p[k].x = a[j].x - a[i].x;
}
}
}
void Quick(int st, int dr)
{
Punct pivot = p[st];
int i = st - 1; int j = dr + 1;
do
{
do { i++; } while ( ((double)pivot.y/(double)pivot.x) > ((double)p[i].y/(double)p[i].x) );
do { j--; } while ( ((double)p[j].y/(double)p[j].x) > ((double)pivot.y/(double)pivot.x) );
if (i <= j)
{
Punct aux = p[i];
p[i] = p[j];
p[j] = aux;
}
} while ( i <= j);
if ( i < dr) Quick(i, dr);
if ( st < j) Quick(st, j);
}