Pagini recente » Cod sursa (job #2327109) | Cod sursa (job #1613804) | Cod sursa (job #2664646) | Cod sursa (job #13579) | Cod sursa (job #3219741)
#include <fstream>
#include <math.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n, nrRele = 0;
double a[10][10];
double x[100], y[100], sir[10];
bool folosit[100], inter[100];
double calc(){
double p1 = 0, p2 = 0;
p1 += a[1][1] * a[2][2] * a[3][3] + a[1][2] * a[2][3] * a[3][1] + a[1][3] * a[2][1] * a[3][2];
p2 += a[3][1] * a[2][2] * a[1][3] + a[3][2] * a[2][3] * a[1][1] + a[3][3] * a[2][1] * a[1][2];
return p1 - p2;
}
double detMat(int pct[]){
for(int i = 1; i <= 3; i++){
a[i][1] = x[pct[i]];
a[i][2] = y[pct[i]];
a[i][3] = 1;
}
return calc();
}
void citire(){
fin >> n;
for(int i = 1; i <= n; i++)
fin >> x[i] >> y[i];
}
bool verificare(int v[]){
bool semn = false;
int s[] = {0, v[1], v[2], v[4]}, aux;
aux = detMat(s);
if(aux == 0)
return false;
if(aux > 0)
semn = true;
s[1] = v[2];
s[2] = v[3];
aux = detMat(s);
if(aux == 0)
return false;
if((aux > 0) != semn)
return false;
s[1] = v[3];
s[2] = v[1];
aux = detMat(s);
if(aux == 0)
return false;
if((aux > 0) != semn)
return false;
return true;
}
void backTrack(int pas){
if(pas == 5){
if(verificare(sir)){// pct interior
inter[sir[4]] = true;
nrRele++;
}
return;
}
for(int i = 1; i <= n; i++){
if(folosit[i])
continue;
if(pas == 4)
if(inter[i])
continue;
folosit[i] = true;
sir[pas] = i;
backTrack(pas + 1);
folosit[i] = false;
}
}
void infasConv(){
backTrack(1);
}
void afisare(){
cout << n - nrRele << "\n";
for(int i = 1; i <= n; i++)
if(!inter[i])
cout << x[i] << " " << y[i] << "\n";
}
int main()
{
citire();
infasConv();
afisare();
return 0;
}