Pagini recente » Cod sursa (job #2428140) | Cod sursa (job #2086258) | Cod sursa (job #2457205) | Cod sursa (job #188376) | Cod sursa (job #2211520)
#include <stdio.h>
#include <algorithm>
#include <bitset>
using namespace std;
FILE *f,*g;
///sens trigonometric=sens antiorar
struct point
{
double x,y;
}v[120002];
int s[120002];
int n,top;
bitset <120002>yes;
bool how(point &a, point &b)
{
if(a.x>b.x)
return (a.x<b.x);
else
if(a.x==b.x)
return (a.y<b.y);
}
void read()
{
fscanf(f,"%d",&n);
for(int i=1;i<=n;++i)
fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,how);
}
///diferenta vectorilor p1p2 si p2p3
///daca e 0 punctele sunt coliniare
///<0 (punctele constituie o orientare in sensul invers acelor de ceasornic),
///>0 (in sensul acelor de ceasornic)
double scanareGhram(point a, point b, point c)
{
return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x));
}
void solve()
{
int ok=1;
s[++top]=1;
s[++top]=2,yes[2]=1;
int i=3;///indicele punctului care urmeaza sa fie verificat pentru a stabili daca se afla pe infasuratoare
while(!yes[1])///nu s-a realizat cel mai optim poligon
{
while(yes[i])
{
if(i==n) ok=-1;
i+=ok;
}
while(top>=2 && scanareGhram(v[s[top-1]],v[s[top]],v[i])>0)
yes[s[top]]=0,--top;
s[++top]=i,yes[i]=1;
}
}
void write()
{
fprintf(g,"%d\n",top-1);
for(int i=top-1;i>=1;--i)
fprintf(g,"%lf %lf\n",v[s[i]].x, v[s[i]].y);
}
int main()
{
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
read();
solve();
write();
fclose(f);
fclose(g);
return 0;
}