Pagini recente » Cod sursa (job #328721) | Cod sursa (job #226392) | Cod sursa (job #770389)
Cod sursa(job #770389)
#include <fstream>
#include <iomanip>
#include <stdlib.h>
using namespace std;
double mydabs(double x)
{
if (x < 0)
{
return -x;
}
return x;
}
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 = mydabs(Cross(x1,y1,x2,y2)) / Dot(x1,y1,x2,y2);
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].X < Points[LowestYIndex].X)
{
LowestYIndex = i;
}
}
Index[0] = LowestYIndex;
Index[LowestYIndex] = 0;
qsort(Index + 1,N - 1,sizeof(int),SortFunc);
Push(LowestYIndex);
Push(Index[1]);
Push(Index[2]);
Index[N] = LowestYIndex;
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;
while (Cross(x1,y1,x2,y2) >= 0)
{
Pop();
x1 = Points[Index[i]].X - Points[Stack[StackPos - 2]].X;
y1 = Points[Index[i]].Y - Points[Stack[StackPos - 2]].Y;
x2 = Points[Stack[StackPos - 1]].X - Points[Stack[StackPos - 2]].X;
y2 = Points[Stack[StackPos - 1]].Y - Points[Stack[StackPos - 2]].Y;
}
Push(Index[i]);
}
StackPos -= 1;
fout << StackPos << "\n";
char OutString[200];
for (int i = 0;i < StackPos;i += 1)
{
sprintf(OutString,"%.6lf %.6lf\n",Points[Stack[i]].X,Points[Stack[i]].Y);
// fout << setprecision(15) << Points[Stack[i]].X << " " << Points[Stack[i]].Y << "\n";
fout << OutString;
}
fin.close();
fout.close();
return 0;
}