Pagini recente » Cod sursa (job #1969913) | Cod sursa (job #2561089) | Cod sursa (job #2097632) | Cod sursa (job #1151868) | Cod sursa (job #770070)
Cod sursa(job #770070)
#include <fstream>
#include <iomanip>
using namespace std;
struct TPoint
{
double X,Y;
};
TPoint Points[125000];
int Index[125000];
int LowestYIndex;
int Stack[125000];
int StackPos;
double Dot(double X1,double Y1,double X2,double Y2)
{
return X1 * X2 - Y1 * Y2;
}
double Cross(double X1,double Y1,double X2,double Y2)
{
return X1 * Y2 - X2 * Y1;
}
int SortFunc(const void *P1,const void *P2)
{
int i1 = *((int *)(P1));
int i2 = *((int *)(P2));
double x1 = Points[i1].X - Points[LowestYIndex].X;
double y1 = Points[i1].Y - Points[LowestYIndex].Y;
double x2 = Points[i2].X - Points[LowestYIndex].X;
double y2 = Points[i2].Y - Points[LowestYIndex].Y;
double res = Cross(x1,y1,x2,y2) / Dot(x1,y1,x2,y2);
if (res > 0)
{
return 1;
}
else
{
return -1;
}
}
void Push(int i)
{
Stack[StackPos] = i;
StackPos += 1;
}
int Pop(void)
{
int res = Stack[StackPos];
StackPos -= 1;
return res;
}
int main(void)
{
fstream fin("infasuratoare.in",ios::in);
fstream fout("infasuratoare.out",ios::out);
long N;
fin >> N;
LowestYIndex = 0;
for (int i = 0;i < N;i += 1)
{
fin >> Points[i].X >> Points[i].Y;
Index[i] = i;
if (Points[i].Y < Points[LowestYIndex].Y)
{
LowestYIndex = i;
}
}
Index[0] = LowestYIndex;
Index[LowestYIndex] = 0;
LowestYIndex = 0;
qsort(Index + 1,N - 1,sizeof(int),SortFunc);
Push(LowestYIndex);
Push(Index[1]);
Push(Index[2]);
for (int i = 3;i < N;i += 1)
{
double x1 = Points[Index[i]].X - Points[Stack[StackPos - 2]].X;
double y1 = Points[Index[i]].Y - Points[Stack[StackPos - 2]].Y;
double x2 = Points[Stack[StackPos - 1]].X - Points[Stack[StackPos - 2]].X;
double y2 = Points[Stack[StackPos - 1]].Y - Points[Stack[StackPos - 2]].Y;
if (Cross(x1,y1,x2,y2) >= 0)
{
Pop();
}
Push(Index[i]);
}
for (int i = 0;i < StackPos;i += 1)
{
fout << setprecision(10) << Points[Stack[i]].X << " " << Points[Stack[i]].Y << "\n";
}
fin.close();
fout.close();
return 0;
}