Pagini recente » Rezultatele filtrării | Cod sursa (job #2150166) | detective | Rezultatele filtrării | Cod sursa (job #714981)
Cod sursa(job #714981)
#include<fstream>
#include<cmath>
#include<iomanip>
#include<algorithm>
#define NMAX 120010
#define EPS 0.00000000001
using namespace std;
struct punct
{
double x, y;
bool vz;
}a[NMAX];
int n, S[NMAX];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
void Citeste()
{
int i;
f>>n;
for (i=1; i<=n; ++i)
f>>a[i].x>>a[i].y;
}
/*inline bool cmp(punct A, punct B)
{
if (A.y==B.y) return A.x<B.x;
return A.y<B.y;
}*/
inline bool cmp(punct A, punct B)
{
if (fabs(A.x-B.x)<EPS)
if (A.y-B.y<EPS) return 1;
else return 0;
else if (A.x-B.x<EPS) return 1;
else return 0;
}
double plan(punct A, punct B, punct C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
void Solve()
{
int i, m;
double P;
S[1]=1; S[2]=2; m=2;
a[2].vz=1;
for (i=3; i<=n; ++i)
{
P=plan(a[S[m-1]], a[S[m]], a[i]);
while (P>0 && m>2) a[S[m]].vz=0, --m, P=plan(a[S[m-1]], a[S[m]], a[i]);
if (P<0) S[++m]=i, a[i].vz=1;
}
for (i=n; i>0; --i)
if (!a[i].vz)
{
P=plan(a[S[m-1]], a[S[m]], a[i]);
while (P>0 && m>2) a[S[m]].vz=0, S[m]=0, --m, P=plan(a[S[m-1]], a[S[m]], a[i]);
if (P<0) S[++m]=i, a[i].vz=1;
}
g<<m-1<<"\n";
for (i=m; i>1; --i)
g<<fixed<<a[S[i]].x<<" "<<a[S[i]].y<<"\n";
}
int main()
{
Citeste();
sort(a+1, a+n+1, cmp);
Solve();
f.close();
g.close();
return 0;
}