Pagini recente » Cod sursa (job #1480761) | Cod sursa (job #1269617) | Cod sursa (job #801302) | Cod sursa (job #3163544) | Cod sursa (job #1898527)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoarea.in");
ofstream fout("infasuratoarea.out");
struct point{
double x,y;
}A[125000],sr;
int N,mpoz;
stack <point> s;
long long dist(point a,point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int direct(point p,point q,point r){
int val=(q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y);
if (val==0) return 0;//colinear
else {
if (val>0) return 1;//clockwise
else return 2;//conterlock wise
}
}
bool comp(point a,point b){
int v=direct(sr,a,b);
if (v==0){
if (dist(sr,b)>=dist(sr,a)) return 0;
else return 1;
}
else {
if (v==2) return 0;
else return 1;
}
}
point nexttotop(){
point p=s.top();
s.pop();
point res=s.top();
s.push(p);
return res;
}
int main(){
fin >>N;
sr.x=sr.y=1e10;
for (int i=1;i<=N;i++){
fin >>A[i].x>>A[i].y;
if (A[i].x<sr.x || (A[i].x==sr.x && A[i].y<sr.y)){
sr=A[i];
mpoz=i;
}
}
swap(A[1],A[mpoz]);
sort(A+2,A+N+1,comp);
//for (int i=1;i<=N;i++) cout <<A[i].x<<" "<<A[i].y<<endl;
s.push(A[1]);
s.push(A[2]);
s.push(A[3]);
//for (int i=3;i<=N;i++) cout <<direct(A[i-2],A[i-1],A[i])<<" ";
for (int i=4;i<=N;i++){
//cout <<s.size()<<" ";
while (direct(nexttotop(),s.top(),A[i])==2 && s.size()>3){
s.pop();
}
s.push(A[i]);
}
fout <<s.size()<<endl;
while (!s.empty()) {
point x=s.top();;
fout <<fixed <<setprecision(6)<<x.x<<" "<<x.y<<"\n";
s.pop();
}
return 0;
}