Pagini recente » Cod sursa (job #481075) | Cod sursa (job #1338350) | Cod sursa (job #2858623) | Cod sursa (job #1605266) | Cod sursa (job #269405)
Cod sursa(job #269405)
#include<cstdio>
#include<algorithm>
using namespace std;
#define INPUT "infasuratoare.in"
#define OUTPUT "infasuratoare.out"
#define NMAX 120001
#define INFI 2000000000
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
struct AngleStruct
{
long double val;
long pos;
};
long N, Pmin;
long Stack[ NMAX ];
long double X[ NMAX ], Y[ NMAX ];
AngleStruct Angle[ NMAX ];
void readData()
{
fscanf(fin, "%ld", &N);
Pmin = 0;
for(long i = 0; i < N; ++i)
{
fscanf(fin, "%Lf %Lf", &X[ i ], &Y[ i ]);
if((X[ Pmin ] > X[ i ]) || (X[ Pmin ] == X[ i ] && Y[ Pmin ] > Y[ i ]))
Pmin = i;
}
}
void detAngles()
{
for(long i = 0; i < N; ++i)
{
if(X[ i ] != X[ Pmin ])
Angle[ i ].val = (Y[ i ] - Y[ Pmin ]) / (X[ i ] - X[ Pmin ]);
else
Angle[ i ].val = INFI;
Angle[ i ].pos = i;
}
}
inline int cmp(AngleStruct _X, AngleStruct _Y)
{
return ((long double)_X.val < (long double)_Y.val)||((long double)_X.val == (long double)_Y.val && (X[_X.pos] < X[_Y.pos] || Y[_X.pos] > Y[_Y.pos]));
}
inline long double sign(long Poz)
{
long V1 = Stack[ Poz - 2 ];
long V2 = Stack[ Poz - 1 ];
long V3 = Stack[ Poz ];
return (X[V1]*Y[V2]+X[V2]*Y[V3]+X[V3]*Y[V1]-Y[V1]*X[V2]-Y[V2]*X[V3]-Y[V3]*X[V1]);
}
void solve()
{
Stack[ 0 ] = Pmin;
long posit = 0;
for(long i = 0; i < N; ++i)
{
Stack[ ++posit ] = Angle[ i ].pos;
/*for(long j = 0; j <= posit; ++j)
fprintf(stderr, "%ld ", Stack[ j ]);
fprintf(stderr, "\n");*/
while(posit >= 2 && sign(posit) < 0)
{
Stack[ posit - 1 ] = Stack[ posit ];
--posit;
}
}
fprintf(fout, "%ld\n", posit);
for(long i = 1; i <= posit; ++i)
fprintf(fout, "%.6Lf %.6Lf\n", X[ Stack[ i ] ], Y[ Stack[ i ] ]);
}
int main()
{
readData();
detAngles();
sort(Angle, Angle + N, cmp);
solve();
fclose(fin);
fclose(fout);
return 0;
}