Pagini recente » Cod sursa (job #1414170) | Cod sursa (job #3225835) | Cod sursa (job #2481917) | Cod sursa (job #1148909) | Cod sursa (job #1344545)
#include <cstdio>
#include <cmath>
#include <list>
#include <algorithm>
#define NMAX 120002
#define INF 1<<29
using namespace std;
FILE* fin=fopen("infasuratoare.in","r");
FILE* fout=fopen("infasuratoare.out","w");
int n;
struct punct
{
double x,y;
double r;
double t;
};
punct pct[NMAX];
list <punct> P;
bool comp(punct a,punct b);
double produs (punct a,punct b,punct c);
void citire();
void afisare();
int main()
{
int i;
citire();
sort(pct+1,pct+n+1,comp);
P.push_back(pct[n]);
for (i=1; i<=n; i++)
P.push_back(pct[i]);
P.push_back(pct[1]);
list<punct>::iterator it;
list<punct>::iterator it1,it2,it3;
it1=it2=it3=P.begin();
it2++; it3++; it3++;
while (it3 != P.end())
{
//afisare();
if (produs (*it1,*it2,*it3)>0)
{
it1++;
it2++;
it3++;
continue;
}
P.erase(it2);
it2=it1;
it1--;
}
//afisare();
fprintf(fout,"%d\n",P.size()-2);
it=P.begin();
it1=P.end(); it1--;
it++;
while (it!=it1)
{
fprintf(fout,"%lf %lf\n",it->x,it->y);
it++;
}
return 0;
}
void citire()
{
int i;
double xmin,ymin;
fscanf(fin,"%d",&n);
xmin=ymin=INF;
for (i=1; i<=n; i++)
{
fscanf(fin,"%lf %lf",&pct[i].x,&pct[i].y);
if (pct[i].x<xmin)
{
xmin=pct[i].x; ymin=pct[i].y;
}
else
{
if (pct[i].x==xmin)
{
if (pct[i].y<ymin)
{
xmin=pct[i].x; ymin=pct[i].y;
}
}
}
}
for (i=1; i<=n; i++)
{
pct[i].r=sqrt((pct[i].x-xmin)*(pct[i].x-xmin) + (pct[i].y - ymin)*(pct[i].y -ymin));
if (pct[i].x != xmin)
pct[i].t=(pct[i].y -ymin)/(pct[i].x-xmin);
else
{
if (pct[i].y == ymin) pct[i].t=-INF;
else pct[i].t=INF;
}
}
}
bool comp(punct a,punct b)
{
if (a.t<b.t) return 1;
if (a.t==b.t) if (a.r<b.r) return 1;
return 0;
}
double produs(punct a,punct b,punct c)
{
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
void afisare()
{
list<punct>::iterator it;
for (it=P.begin(); it!=P.end(); it++)
{
fprintf(fout,"%.0lf %.0lf ",it->x,it->y);
}
fprintf(fout,"\n");
}