Pagini recente » Cod sursa (job #2780629) | Cod sursa (job #2891934) | Cod sursa (job #1165707) | Cod sursa (job #94897) | Cod sursa (job #3273299)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <float.h>
#include <iomanip>
using namespace std;
const double INF = DBL_MAX;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Pont
{
double x;
double y;
double slope;
};
double slope(Pont start, Pont veg)
{
if(veg.y - start.y == 0){
return INF;
}
return -(veg.x-start.x)/(veg.y-start.y);
}
bool comp(Pont p1, Pont p2)
{
return (p1.slope < p2.slope);
}
double crossProduct(Pont p1, Pont p2, Pont p3)
{
return (p2.x*p3.y + p1.x*p2.y + p3.x*p1.y - p2.x*p1.y - p3.x*p2.y - p1.x*p3.y);
}
/*
|1 1 1 |
|x1 x2 x3|= x1y2 + x2y3 + x3y1 - x3y2 - x2y1 - x1y3
|y1 y2 y3|
*/
int main()
{
int N;
fin >> N;
vector<Pont> pontok(N);
int startPont = 0;
Pont start;
for(int i = 0; i < N; i++){
fin >> pontok[i].x >> pontok[i].y;
if(pontok[startPont].y > pontok[i].y){
startPont = i;
}
else if(pontok[startPont].y == pontok[i].y && pontok[startPont].x > pontok[i].x){
startPont = i;
}
}
for(int i = 0; i < N; i++){
pontok[i].slope = slope(pontok[startPont], pontok[i]);
}
/*for(int i = 0; i < N; i++){
cout << slope(pontok[startPont], pontok[i]) << endl;
}*/
start = pontok[startPont];
//cout << pontok[startPont].x << " " << pontok[startPont].y << endl;
//cout << start.x << " " << start.y << endl << endl;
sort(pontok.begin(), pontok.end(), comp);
for(int i = 0; i < N; i++){
if(pontok[i].x == start.x && pontok[i].y == start.y){
startPont = i;
break;
}
}
int secondToLast;
stack<int> st;
st.push(startPont);
st.push(0);
for(int i = 1; i < N; i++){
if(i == startPont){
continue;
}
int temp = st.top();
st.pop();
secondToLast = st.top();
st.push(temp);
while(crossProduct(pontok[secondToLast], pontok[st.top()], pontok[i]) <= 0 && st.size() >= 2){
st.pop();
if(st.size() < 2){
break;
}
temp = st.top();
st.pop();
secondToLast = st.top();
st.push(temp);
}
st.push(i);
}
stack<int> result;
while(!st.empty()){
result.push(st.top());
st.pop();
}
fout << result.size() << endl;
while(!result.empty()){
fout << fixed << setprecision(6) << pontok[result.top()].x << " " << pontok[result.top()].y << endl;
result.pop();
}
return 0;
}