Pagini recente » Cod sursa (job #589557) | Cod sursa (job #2545901) | Cod sursa (job #2394737) | Cod sursa (job #2510619) | Cod sursa (job #964971)
Cod sursa(job #964971)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Point
{
double x, y;
};
Point points[120005];
vector<Point> stive;
#define inf 1000000005.0
#define lng stive.size()-1
int N;
double dot_product(Point P0, Point P1, Point P2)
{
return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}
bool cmp(Point P1, Point P2)
{
return dot_product(points[0],P1,P2) < 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> N;
for(int i = 0; i < N; ++i)
{
f >> points[i].x >> points[i].y;
}
Point min;
min.x = 1000000005.0;
min.y = 1000000005.0;
for(int i = 0; i < N; ++i)
{
if( points[i].y < min.y || ( points[i].y == min.y && points[i].x < min.x))
{
min.x = points[i].x;
min.y = points[i].y;
}
}
cout<<"Minimum:"<<min.x<<" "<<min.y<<endl;
swap(min,points[0]);
sort(points+1, points+N, cmp);
for(int i = 0; i< N;i++)
cout<<"X: "<<points[i].x<<" "<<"Y: "<<points[i].y<<" "<<endl;
cout<<"----------------------------------------------"<<endl;
stive.push_back(points[0]);
stive.push_back(points[1]);
//stive.push_back(points[2]);
for(int i = 0; i< stive.size(); i++)
cout<<"X: "<<stive[i].x<<" "<<"Y: "<<stive[i].y<<" "<<endl;
cout<<"----------------------------------------------"<<endl;
for( int i=2; i<N; i++)
{
while(stive.size() > 1 && dot_product(stive[lng-1], stive[lng], points[i]) > 0)
{
stive.pop_back();
}
stive.push_back(points[i]);
}
cout<<"size: "<<stive.size()<<endl;
for(int i = 0; i<=lng; ++i)
cout<<"X: "<<stive[i].x<<" "<<"Y: "<<stive[i].y<<" "<<endl;
cout<<"-----------------------------------------------------"<<endl;
for(int i = lng; i>=0; --i)
cout<<"X: "<<stive[i].x<<" "<<"Y: "<<stive[i].y<<" "<<endl;
return 0;
}