Pagini recente » Istoria paginii runda/simulare05032019/clasament | Cod sursa (job #1152357) | Cod sursa (job #2456780) | Cod sursa (job #2844302) | Cod sursa (job #1038232)
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
const double eps = 1.e-14;
struct POINT {
double x,y;
POINT (double x=0, double y=0) {
this -> x = x;
this -> y = y;
}
};
vector <POINT> p,st;
int ccw (POINT P1, POINT P2, POINT P3) {
double cp = (P2.x - P1.x) * (P3.y - P2.y) - (P2.y - P1.y) * (P3.x - P2.x);
if(cp < 0)
return -1;
if(cp > 0)
return 1;
return 0;
}
class cmp {
public:
bool operator () (POINT a, POINT b) {
return ccw(p[0],a,b) > 0;
}
};
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int i,n;
double x,y;
scanf("%d",&n);
for(i = 0; i < n; i++) {
scanf("%lf%lf",&x,&y);
p.push_back(POINT(x,y));
}
for(i = 1; i < n; i++)
if(p[i].x < p[0].x || (fabs(p[i].x - p[0].x) < eps && p[i].y < p[0].y))
swap(p[i],p[0]);
sort(p.begin(),p.end(),cmp());
p.push_back(p[0]);
i = 0;
while(i < p.size()) {
if(st.size() < 2 || ccw(st[st.size() - 2],st[st.size() - 1],p[i]) > 0) {
st.push_back(p[i]);
i++;
}
else
st.erase(st.end() - 1);
}
printf("%d\n",st.size());
for(i = 1; i < st.size(); i++) {
printf("%lf %lf\n",st[i].x,st[i].y);
}
return 0;
}