Pagini recente » Cod sursa (job #1609351) | Cod sursa (job #94141) | Cod sursa (job #1985732) | Cod sursa (job #12895) | Cod sursa (job #697676)
Cod sursa(job #697676)
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
FILE *g=fopen("infasuratoare.out","w");
struct punct
{
double x,y;
} p[120001];
int s[120001],r,k,infinit,v[120001],vf,n;
char nr[31];
void citire()
{
f>>n;
for(int i=1;i<=n;i++) f>>p[i].x>>p[i].y;
f.close();
}
void reper()
{
r=1;
for(int i=2;i<=n;i++)
if(p[i].x<p[r].x||p[i].x==p[r].x&&p[i].y<p[r].y) r=i;
}
int mai_mic(int i,int j)
{
double a=(p[i].x-p[r].x)*(p[j].x-p[r].x);
double b=(p[i].y-p[r].y)*(p[j].x-p[r].x)-(p[i].x-p[r].x)*(p[j].y-p[r].y);
if(a<0&&b>0||a>0&&b<0) return 1;
return 0;
}
void ordonare()
{
k=0;
int i;
for(i=1;i<=n;i++)
if(i!=r)
if(p[i].x==p[r].x)
if(!infinit||p[infinit].y<p[i].y) infinit=i;
else;
else k++, v[k]=i;
sort(v+1,v+k+1,mai_mic);
}
int elim(int i)
{
double a=p[v[i]].x-p[s[vf]].x;
double b=(p[s[vf-1]].y-p[v[i]].y)*a-(p[v[i]].y-p[s[vf]].y)*(p[s[vf-1]].x-p[v[i]].x);
if(b<=0) return 1;
return 0;
}
void stiva()
{
s[1]=r;
s[2]=v[1];
vf=2;
for(int i=2;i<=k;i++)
{
while(elim(i)&&vf>2) vf--;
vf++;
s[vf]=v[i];
}
}
void afis()
{
if(infinit) fprintf(g,"%d\n",vf+1);
else fprintf(g,"%d\n",vf);
for(int i=1;i<=vf;i++) fprintf(g,"%.6lf %.6lf\n",p[s[i]].x,p[s[i]].y);
if(infinit)fprintf(g,"%.6lf %.6lf\n",p[infinit].x,p[infinit].y);
}
int main()
{
citire(); reper(); ordonare(); stiva(); afis();
fclose(g);
return 0;
}