Pagini recente » Cod sursa (job #1058578) | Cod sursa (job #2003994) | Cod sursa (job #1037366) | Cod sursa (job #2364046) | Cod sursa (job #903548)
Cod sursa(job #903548)
#include <stdio.h>
#include <cmath>
#include <Windows.h>
#define NMAX 120005
#define INF 1<<30
FILE *f=fopen ("infasuratoare.in", "r");
FILE *g=fopen ("infasuratoare.out", "w");
struct Point2D { double x, y, slope; //parametrul id folosit pentru a verifica daca in GrahamScan se face corect excluderea nodurilor
int id; } v[NMAX], aux[NMAX], p;
int st[NMAX];
int n, k;
void read()
{
p.x = p.y = INF;
fscanf (f, "%d", &n);
for (int i = 0; i < n ; i++)
{
fscanf (f, "%lf%lf", &v[i].x, &v[i].y);
v[i].id = i;
if (p.y > v[i].y) p = v[i];
else if (p.y == v[i].y && p.x > v[i].x) p = v[i];
}
}
void calculateSlope(Point2D v[], Point2D p) //calculeaza panta dreptei dintre V[i] si P
{
for (int i = 0; i < n; i++)
if (v[i].id != p.id)
if (v[i].x != p.x) v[i].slope = (v[i].y - p.y)/(v[i].x - p.x);
else v[i].slope = INF;
}
void Merge(Point2D v[], int lo, int mid, int hi)
{
for (int i = lo; i <= hi; i++) //copiaza intr-un vector auxiliar
aux[i] = v[i];
int i = lo;
int j = mid+1;
for (int k = lo; k <= hi; k++) //interclasarea
{
if (i > mid) v[k] = aux[j++];
else if (j > hi) v[k] = aux[i++];
else if (aux[i].slope < aux[j].slope) v[k] = aux[i++];
else v[k] = aux[j++];
}
}
void MergeSort(Point2D v[], int lo, int hi)
{
int mid = lo + (hi-lo)/2;
if (hi <= lo) return;
MergeSort(v, lo, mid);
MergeSort(v, mid+1, hi);
Merge(v, lo, mid, hi);
}
void rearrange(Point2D v[])
{
int j = 0;
for (int i = 0; i < n && v[i].slope < 0; i++)
aux[j++] = v[i];
for (int i = 0; i < n; i++)
if ( i < n - j) v[i] = v[i+j];
else v[i] = aux[i-n+j];
}
bool CounterClockWise(Point2D A, Point2D B, Point2D C) // | Ax Ay 1 |
{ // | Bx By 1 | = (Bx - Ax)(By - Ay) - (By - Ay)(Cx - Ax)
float val; // | Cx Cy 1 |
val = (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x); //Counterclockwise rotation if area is > 0
return val > 0;
}
void GrahamScan(Point2D v[])
{
st[k++] = 0;
st[k++] = 1;
for (int i = 2; i < n; i++)
{
while ( !CounterClockWise(v[st[k-2]], v[st[k-1]], v[i]) )
k--;
st[k++] = i;
}
}
int main()
{
read();
calculateSlope(v, p);
MergeSort(v, 0, n-1);
rearrange(v);
/* for (int i = 0; i < n; i++) //tipareste ordinea punctelor sortate dupa unghiul polar
fprintf (g, "Point %c: %f\n", (char)(65+v[i].id), v[i].slope); //folosit pentru a verifica daca sortarea se face corect
*/
GrahamScan(v);
fprintf (g, "%d\n", k);
for (int i = 0; i < k; i++)
fprintf (g, "%lf %lf\n", v[st[i]].x, v[st[i]].y);
return 0;
}