Pagini recente » Cod sursa (job #938828) | Cod sursa (job #1241399) | Cod sursa (job #2619673) | Cod sursa (job #1699628) | Cod sursa (job #1946275)
#include <bits/stdc++.h>
/**
`-.`'.-'
`-. .-'.
`-. -./\.- .-'
-. /_|\ .-
`-. `/____\' .-'.
`-. -./.-""-.\.- '
`-. /< (()) >\ .-'
- .`/__`-..-'__\' .-
,...`-./___|____|___\.-'.,.
,-' ,` . . ', `-,
,-' ________________ `-,
,'/____|_____|_____\
/ /__|_____|_____|___\
/ /|_____|_____|_____|_\
' /____|_____|_____|_____\
.' /__|_____|_____|_____|___\
,' /|_____|_____|_____|_____|_\
,,---''--...___...--'''--.. /../____|_____|_____|_____|_____\ ..--```--...___...--``---,,
'../__|_____|_____|_____|_____|___\
\ ) '.:/|_____|_____|_____|_____|_____|_\ ( /
)\ / ) ,':./____|_____|_____|_____|_____|_____\ ( \ /(
/ / ( ( /:../__|_____|_____|_____|_____|_____|___\ ) ) \ \
| | \ \ /.../|_____|_____|_____|_____|_____|_____|_\ / / | |
.-.\ \ \ \ '..:/____|_____|_____|_____|_____|_____|_____\ / / / /.-.
(= )\ `._.' | \:./ _ _ ___ ____ ____ _ _ _ _ _ _ _ __\ | `._.' /( =)
\ (_) ) \/ \ ( (_) /
\ `----' """""""""""""""""""""""""""""""""""""""""""""" `----' /
\ ____\__ __/____ /
\ (=\ \ / /-) /
\_)_\ \ / /_(_/
\ \ / /
) ) _ _ ( (
( (,-' `-..__ __..-' `-,) )
\_.-'' ``-..____ ____..-'' ``-._/
`-._ ``--...____...--'' _.-'
`-.._ _..-'
`-..__ AKRIEL __..-'
``-..____ ____..-''
``--...____...--''
*/
using namespace std;
#define coordonates pair <double, double>
#define x first
#define y second
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N {120005};
/*
struct coordonates{
double x;
double y;
coordonates (void){
};
coordonates (double x, double y){
this->x = x;
this->y = y;
}
bool lowerThan(coordonates B){
if ( y < B.y )
return true;
if ( x < B.x and y == B.y )
return true;
return false;
}
};
*/
coordonates points[N], leftBottom, Stack[N] ;
int totalPoints, positionLeftBottom, top;
double aria(coordonates A, coordonates B, coordonates C){
return A.x*B.y + B.x*C.y + C.x*A.y - C.x*B.y - B.x*A.y - A.x*C.y;
}
double epsilon = 0.00000001;
bool compare(coordonates A, coordonates B, coordonates C = points[1]){
double delta = aria(A, B, C);
if ( delta > epsilon )
return true;
if ( delta < -epsilon )
return false;
return false;
}
bool trigger(coordonates A, coordonates B){
return compare(A, B);
}
inline void readVariables(void){
double x, y;
fin >> totalPoints;
fin >> x >> y;
points[1] = {x, y};
leftBottom = points[1];
positionLeftBottom = 1;
for ( int index = 2; index <= totalPoints; index++ ){
fin >> x >> y;
points[index] = {x, y};
if ( points[index] < leftBottom ){
positionLeftBottom = index;
leftBottom = points[index];
}
}
swap(points[positionLeftBottom], points[1]);
}
inline void convexHull(void){
Stack[1] = points[1];
Stack[2] = points[2];
top = 2;
for ( int index = 3; index <= totalPoints; index++ ){
for ( ; !compare(Stack[top-1], Stack[top], points[index]); )
top--;
Stack[++top] = points[index];
}
}
inline void displayPoints(void){
for ( int index = 1; index <= totalPoints; index++ )
cout << points[index].x << " " << points[index].y << "\n";
cout << "\n";
}
inline void solveProblem(void){
sort (points+1, points+totalPoints+1, trigger);
convexHull();
fout << top << "\n";
for ( int index = 1; index <= top; index++ )
fout << fixed << setprecision(5) << Stack[index].x << " " << Stack[index].y << "\n";
}
int main(){
readVariables();
solveProblem();
}