Pagini recente » Cod sursa (job #73455) | Cod sursa (job #1819832) | Cod sursa (job #1712337) | Cod sursa (job #1348627) | Cod sursa (job #3159629)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct puncte
{
double x, y;
};
puncte a[120005];
puncte b[120005];
///aici pun punctele finale
int k=0; ///nr de puncte ale poligonului convex
int n;
bool comparexpoints(puncte a1, puncte a2)
{
if(a1.x==a2.x)
{
if(a1.y>a2.y)
return 1;
else return 0;
}
else if(a1.x<a2.x)
return 1;
return 0;
}
enum orientare{
TRIGONOMETRIC,
ORAR,
COLIN
};
orientare calcOrientare(puncte p1, puncte p2, puncte p3)
{
double det=(p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
if(det<0)
return TRIGONOMETRIC;
else if(det>0)
return ORAR;
else
return COLIN;
}
void parcurgereinfasuratorsus()
{
for(int i=0; i<n; i++)
{
///testez daca merge bagat punctul a[i]
while(k>=2 && calcOrientare(b[k - 2], b[k - 1], a[i])!=ORAR)
{
k--;
}
b[k++]=a[i];
}
}
void parcurgereinfasuratorjos()
{
for(int i=n-2; i>=0; i--)
{
///testez daca merge bagat punctul a[i]
while(k>=2 && calcOrientare(b[k - 2], b[k - 1], a[i])!=ORAR)
{
k--;
}
b[k++]=a[i];
}
}
int main()
{
fin >> n;
for(int i=0; i<n; i++)
fin >> a[i].x >> a[i].y;
sort(a, a+n, comparexpoints);
parcurgereinfasuratorsus();
parcurgereinfasuratorjos();
k--;
fout << k << "\n";
for(int i=0; i<k; i++)
fout << fixed << setprecision(6) << b[i].x << " " << b[i].y << '\n';
return 0;
}