Pagini recente » Cod sursa (job #923652) | Cod sursa (job #2180926) | Cod sursa (job #2200552) | Cod sursa (job #944839) | Cod sursa (job #1802932)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
FILE*fin = fopen("infasuratoare.in", "r");
FILE*fout = fopen("infasuratoare.out", "w");
struct Point
{
double x, y;
};
bool sign(const Point* p1,const Point* p2,const Point* p3)
{
return (p1->x*p2->y + p2->x*p3->y + p3->x*p1->y - p1->x*p3->y - p2->x*p1->y - p3->x*p2->y) > 0;
}
Point* startPoint;
bool myComp1(const Point* my,const Point* other)
{
return sign(startPoint, my, other) == false;
}
bool myComp2(const Point* my, const Point* other)
{
return my->y<other->y;
}
int main()
{
int nrOfPoints;
double p=100;
vector<Point*> points,hull;
Point* current,low;
fscanf(fin,"%d", &nrOfPoints);
low.x = 100;
low.y = 100;
for (int i = 0; i < nrOfPoints; i++)
{
current = new Point;
fscanf(fin, "%lf %lf", ¤t->x, ¤t->y);
if (low.y<current->y)
{
low.y = current->y;
low.x = current->x;
}
points.push_back(current);
}
sort(points.begin(), points.end(),myComp2);
startPoint = new Point;
startPoint->x = points[0]->x;
startPoint->y = points[0]->y;
sort(points.begin()+1, points.end(), myComp1);
hull.push_back(startPoint);
hull.push_back(points[1]);
for (auto it = points.begin() + 2; it != points.end(); it++)
{
auto second = hull.end() - 2;
auto first = hull.end() - 1;
while (sign(*second, *first, *it) == true)
{
hull.erase(first);
first = second;
second --;
}
hull.push_back(*it);
}
int pos = 0;
for (auto i : hull)
{
if (i->y == p)
pos++;
}
std::rotate(hull.begin(), hull.begin() + pos+1, hull.end());
fprintf(fout, "%d\n", hull.size());
for (auto i=hull.rbegin();i!=hull.rend();i++)
{
fprintf(fout,"%lf %lf\n", (*i)->x, (*i)->y);
}
}