Pagini recente » Cod sursa (job #2315510) | Cod sursa (job #2217663) | Cod sursa (job #1046273) | Cod sursa (job #1287274) | Cod sursa (job #2545459)
#include<stdio.h>
#include<algorithm>
#include <stdio.h>
#define nmax 120010
#define INF 1<<30 //2 la 30
using namespace std;
int i,n,k,s[nmax],poz;
struct punct
{
double x,y,panta;
} v[nmax],o,aux;
int cmp ( punct a, punct b)
{
if(a.panta==b.panta) return a.x<b.x;
return a.panta<b.panta;
}
int convex()
{
punct a,b,c;
double nr;
a=v[s[k-1]];
b=v[s[k]];
c=v[i];
nr = ( a.x-c.x ) * ( b.y-a.y ) + ( a.x-b.x ) * ( a.y-c.y ) ;
if(nr > 0) {
return 1;
}
return 0;
}
int main()
{
FILE*in = fopen("infasuratoare.in", "r");
FILE*out = fopen("infasuratoare.out", "w");
fscanf(in, "%d",&n);
o.x=o.y=INF;
for(i = 1;i <= n; i++)
{
fscanf(in, "%lf %lf",&v[i].x,&v[i].y);
if(v[i].x < o.x || v[i].x == o.x && v[i].y < o.y) {
o=v[i];
poz=i;
}
}
aux=v[1]; v[1]=v[poz]; v[poz]=aux;
for(i = 2; i <= n; i++) {
v[i].panta = (v[i].y - o.y)/(v[i].x - o.x);
}
sort(v+2, v+n+1, cmp);
s[1]=1; s[2]=2; k=2;
for(i=3;i<=n;i++)
{
while (!convex() && k>2) {
k--;
}
s[++k]=i;
}
fprintf(out, "%d\n",k);
for(i=1;i<=k;i++)
fprintf(out, "%0.6lf %0.6lf\n",v[s[i]].x,v[s[i]].y);
return 0;
}