Pagini recente » Cod sursa (job #2760313) | Cod sursa (job #1794585) | Cod sursa (job #1285133) | Cod sursa (job #247743) | Cod sursa (job #1021619)
#include<iostream>
#include<fstream>
#include<algorithm>
#define rad3 1.73205081
#include<cstdlib>
#include<ctime>
using namespace std;
typedef struct punct{
double x;
double y;}pct;
pct p[1500];
double eps=10e-3;
pct pivot(int left, int right)
{
pct p1;
p1=p[left + rand() % (right-left+1)];
return p1;
}
int cmp(pct a, pct b)
{
if(a.x-b.x<eps&&a.x-b.x>-eps)
{if(a.y-b.y<eps&&a.y-b.y>-eps)
return 0;
else
if(a.y-b.y>eps)
return 1;
else return -1;
}
if(a.x-b.x>eps)
return 1;
return -1;
}
void quicksort(int left, int right)
{
int i=left, j=right;
double tmpo;
pct tmp, piv;
piv=pivot(left,right);
while(i<=j)
{
while(p[i].x<piv.x)
i++;
while(p[j].x>piv.x)
j--;
if(i<=j)
{
tmp=p[i];
p[i]=p[j];
p[j]=tmp;
if(p[i].x==p[j].x)
if(p[i].y>p[j].y){
tmpo=p[i].y;
p[i].y=p[j].y;
p[j].y=tmpo;
}
i++;
j--;
}
}
if(left<j)
quicksort(left,j);
if(i<right)
quicksort(i,right);
}
int caut(pct r, int left, int right)
{
int m;
if(left<=right)
{
m=(left+right)/2;
if(cmp(p[m],r)==0)
return 1;
else
if(cmp(p[m],r)<0)
return caut(r,m+1,right);
else
return caut(r,left,m-1);
}
else
return 0;
}
int main()
{
int n,i,j;
double x1, y1;
ifstream f("triang.in");
ofstream g("triang.out");
f>>n;
pct aux;
for(i=0;i<n;i++)
f>>p[i].x>>p[i].y;
quicksort(0,n-1);
int nr=0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
x1=p[i].x+p[i].y*rad3+p[j].x-p[j].y*rad3;
y1=-p[i].x*rad3+p[i].y+p[j].y+p[j].x*rad3;
aux.x=x1/2.0;
aux.y=y1/2.0;
if(caut(aux,0,n-1)==1)
nr++;
x1=p[i].x+p[j].x+(p[j].y-p[i].y)*rad3;
y1=p[i].x*rad3+p[j].y+p[i].y-p[j].x*rad3;
aux.x=x1/2.0;
aux.y=y1/2.0;
if(caut(aux,0,n-1)==1)
nr++;
}
g<<nr/3;
}