Pagini recente » Cod sursa (job #1944436) | Cod sursa (job #2504995) | Cod sursa (job #3249312) | Cod sursa (job #2549288) | Cod sursa (job #844014)
Cod sursa(job #844014)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#ifndef M_PI
#define M_PI 3.141592654
#endif
typedef struct Point{
double x;
double y;
double angle;
}Point;
double get_angle(double x1, double y1, double x2, double y2)
{
if( x1 == x2 )
return M_PI/2;
else
return atan((y2-y1)/(x2-x1));
}
double get_angle(Point p1, Point p2)
{
return get_angle(p1.x,p1.y,p2.x,p2.y);
}
//////////// STACK //////////////////////
typedef struct tagNode
{
Point value;
struct tagNode *next;
}Node;
struct Stack
{
Node* start;
Stack(){
this->start = NULL;
}
void push(Point value){
Node *niu = new Node;
niu->next = this->start;
niu->value = value;
this->start = niu;
}
Point top(){
return this->start->value;
}
void pop(){
Node* toDelete = this->start;
this->start = this->start->next;
delete toDelete;
}
int isEmptyStack(){
return this->start == NULL;
}
};
////////////////////////////////////////
#define MAXN 120000
int N;
Point points[MAXN];
Stack solution;
int count;
int compare(const void *pt1, const void *pt2)
{
return ((Point*)pt1)->angle < ((Point*)pt2)->angle;
}
int main(int argc, char* argv[])
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
int startPos = 0;
int i;
for(i=0;i<N;i++){
scanf("%lf %lf",&points[i].x,&points[i].y);
if( (points[i].x < points[startPos].x) ||
(points[i].x == points[startPos].x && points[i].y < points[startPos].y))
startPos = i;
}
Point aux = points[startPos];
points[startPos] = points[0];
points[0] = aux;
for(i=1;i<N;i++){
points[i].angle = get_angle(points[0],points[i]);
}
qsort(points+1,N-1,sizeof(Point),compare);
solution.push(points[0]);
solution.push(points[1]);
count = 2;
for(i=2;i<N;i++){
#define p1 (solution.start->next->value)
#define p2 (solution.start->value)
#define p3 (points[i])
while( (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x) > 0 ){
solution.pop();
count--;
}
solution.push(points[i]);
count++;
}
printf("%d\n",count);
Node* q = solution.start;
while(q != NULL){
printf("%lf %lf\n",q->value.x,q->value.y);
q=q->next;
}
return 0;
}