Pagini recente » Cod sursa (job #1660402) | Cod sursa (job #2528777) | Cod sursa (job #1876601) | Cod sursa (job #2104796) | Cod sursa (job #2169211)
#include<bits/stdc++.h>
#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"
#define x first
#define y second
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
typedef pair<double,double> Point;
int N;
vector<Point> points;
Point reper{0,0};
void Read(){
in>>N;
for(int i=1;i<=N;i++){
double cx,cy;
in>>cx>>cy;
points.push_back({cx,cy});
}
}
double CrossProduct(Point P0, Point P1, Point P2){
return (P1.x-P0.x)*(P2.y-P0.y)-(P1.y-P0.y)*(P2.x-P0.x);
}
bool comp( Point A, Point B){
return CrossProduct(reper,A,B)<0;
}
void AfisPoints(){
for(auto p:points){
cout<<p.x<<" "<<p.y<<"\n";
}
}
void Sortare(){
int pozPoint=0;
Point px=points[pozPoint];
for(int i=1;i<points.size();i++){
if(points[i].x<px.x){
px=points[i];
pozPoint=i;
}
else if(points[i].x==px.x&&points[i].y<px.y){
px=points[i];
pozPoint=i;
}
}
swap(points[0],points[pozPoint]);
reper=points[0];
sort(points.begin()+1,points.end(),comp);
//AfisPoints();
}
Point Top(vector<Point>&s){
return s.back();
}
Point Top2(vector<Point>&s){
return s[s.size()-2];
}
void GrahamScan(){
vector<Point> st;
st.push_back(points[0]);
st.push_back(points[1]);
for(int i=2;i<points.size();i++){
while(st.size()>=2&&CrossProduct(Top2(st),Top(st),points[i])>0)
st.pop_back();
st.push_back(points[i]);
}
out<<st.size()<<"\n";
for(int i=st.size()-1;i>=0;i--){
out<<fixed<<setprecision(9)<<st[i].x<<" "<<st[i].y<<"\n";
}
}
int main(){
Read();
Sortare();
GrahamScan();
return 0;
}