Pagini recente » Cod sursa (job #2574049) | Cod sursa (job #1613599) | Cod sursa (job #2276851) | Cod sursa (job #193539) | Cod sursa (job #1348952)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct p{double x,y;};
// <0 --> CW
// >0 --> CCW
//==0 --> COLLINEAR
int isccw(p &p1,p &p2,p &p3){
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
p p0;
bool cmp(p p1,p p2){
return isccw(p0,p1,p2)>0;
}
int main(){
ifstream ifs("infasuratoare.in");
ofstream ofs("infasuratoare.out");
int N;
ifs>>N;
vector<p> v(N); //pontok
int c=0;
for(int i=0;i<N;i++){
ifs>>v[i].x>>v[i].y;
if(v[i].x<v[c].x)
c=i;
}
p t=v[0]; v[0]=v[c]; v[c]=t; p0=v[0];
sort(v.begin()+1,v.end(),cmp);
int s[120005]; s[0]=0; s[1]=1;
int top=1;
for(int i=2;i<N;i++){
while(top>=1 && isccw(v[s[top-1]],v[s[top]],v[i])<0)
top--;
top++;
s[top]=i;
}
ofs<<top+1<<"\n";
ofs<<setprecision(10);
for(int i=0;i<=top;i++){
ofs<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
}
}