Pagini recente » Cod sursa (job #87070) | Cod sursa (job #2561395) | Cod sursa (job #375630) | Cod sursa (job #2927671) | Cod sursa (job #1807306)
#include <iostream>
#include <algorithm>
#include <cstdio>
#define nmax 120001
using namespace std;
FILE *f=fopen("infasuratoare.in", "r");
FILE *g=fopen("infasuratoare.out", "w");
struct point
{
float x, y;
} p[nmax];
int n;
void Citire()
{
int i;
fscanf(f, "%d", &n);
for(i=1; i<=n; i++)
fscanf(f, "%f%f", &p[i].x, &p[i].y);
//n++;
//p[n].x=p[n].y=0;
}
bool comp(point p1, point p2)
{
float v1, v2;
v1=(float) (p1.y-p[1].y)/(p1.x-p[1].x);
v2=(float) (p2.y-p[1].y)/(p2.x-p[1].x);
if(v1>v2) return false; //
return true;
}
void SortPoints()
{
int i, poz;
poz=1;
for(i=1; i<=n; i++)
if(p[i].x<p[poz].x)
poz=i;
else if(p[poz].x==p[i].x)
if(p[poz].y<p[i].y)
poz=i;
point aux;
aux=p[1];
p[1]=p[poz];
p[poz]=aux;
sort(p+2, p+n+1, comp);
}
int sens(point p1, point p2, point p3)
{
int var, sol;
var=p1.x*p2.y+p2.x*p3.y+p1.y*p3.x-p3.x*p2.y-p3.y*p1.x-p2.x*p1.y;
if(var<0) return -1;
if(var>0) return 1;
return 0;
}
void CreatePolygon()
{
int stiva[nmax]={0}, top, it, j, bun, i;
stiva[1]=1;
stiva[2]=2;
top=2; it=3;
while(stiva[top]!=1)
{
top++; stiva[top]=it;
bun=1;
for(i=1; i<=n; i++)
if(sens(p[stiva[top-1]], p[stiva[top]], p[i])<0)
{
top--;
it=i;
bun=0;
}
if(bun)
it++;
if(it>n) it=1;
}
top--;
/*
//daca sunt noduri coliniare in infasuratoarea convexa
for(i=2; i<top; i++)
if((p[stiva[i]].x==p[stiva[i-1]].x)&&(p[stiva[i]].x==p[stiva[i+1]].x))
top--;
if(p[stiva[top]].x==p[stiva[1]].x&&p[stiva[1]].x==p[stiva[2]].x)
top--;
if(p[stiva[top-1]].x==p[stiva[top]].x&&p[stiva[top]].x==p[stiva[1]].x)
top--;
for(i=2; i<top; i++)
if(p[stiva[i]].y==p[stiva[i-1]].y&&p[stiva[i]].y==p[stiva[i+1]].y)
top--;
if(p[stiva[top]].y==p[1].y&&p[1].y==p[2].y)
top--;
if(p[top-1].y==p[stiva[top]].y&&p[stiva[top]].y==p[1].y)
top--;
*/
fprintf(g, "%d\n", top);
for(i=1; i<=top; i++)
fprintf(g, "%f %f\n", p[stiva[i]].x, p[stiva[i]].y);
}
int main()
{
Citire();
SortPoints();
CreatePolygon();
fclose(f);
fclose(g);
return 0;
}