Pagini recente » Cod sursa (job #1106504) | Cod sursa (job #3238519) | Cod sursa (job #2950563) | Diferente pentru implica-te/arhiva-educationala intre reviziile 94 si 223 | Cod sursa (job #3149296)
#include <bits/stdc++.h>
#include <cstring>
#include <cstdio>
#pragma GCC optimize ("O3")
#define din cin
#define dout out
#define pi 3.14159265359
#define sw(x,y) x^=y,y^=x,x^=y
#define bmin(a,b)((a<b)?(a):(b))
#define bmax(a,b)((a>b)?(a):(b))
#define bminify(a,b)a=bmin(a,b)
#define bmaxify(a,b)a=bmax(a,b)
#define forq(i,ii,n)for(i=ii;i<n;i++)
#define f first
#define s second
#define mod 1000000297ll
#define nmax 120002
using namespace std;
typedef long long ll;
ifstream in("ghicit.in");
ofstream out("cuba.out");
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
struct p{double x,y,u;}t[nmax];
int n,i,j,k,l,c[nmax]={0,1};
int main()
{
fscanf(fin,"%d",&n);
for(i=0;i<n;i++)
{
fscanf(fin,"%lf %lf",&t[i].x,&t[i].y);
if(t[i].y<t[k].y||(t[i].y==t[k].y&&t[i].x<t[k].x))k=i;
}
if(k)swap(t[0],t[k]);
t[n]=t[0];
//printf("%lf %lf",t[0].x,t[0].y);
for(i=1;i<n;i++)t[i].u=(t[i].x-t[0].x)/(t[i].y-t[0].y);//CTG
sort(t+1,t+n,[](p a,p b){return a.u>b.u;});
//for(i=1;i<n;i++)cout<<t[i].x-t[0].x<<' '<<t[i].y-t[0].y<<'\n';
for(i=2;i<=n;i++)
{
while(l&&t[c[l]].y*(t[i].x-t[c[l+1]].x)+t[c[l+1]].y*(t[c[l]].x-t[i].x)+t[i].y*(t[c[l+1]].x-t[c[l]].x)<=0)--l;
c[++l+1]=i;
}
fprintf(fout,"%d",l+1);
for(i=0;i<=l;i++)fprintf(fout,"\n%.6lf %.6lf",t[c[i]].x,t[c[i]].y);
}