Pagini recente » Cod sursa (job #928200) | Cod sursa (job #2745739) | Cod sursa (job #1553010) | Cod sursa (job #44157) | Cod sursa (job #1349299)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct p{double x,y;};
// <0 --> CW // >0 --> CCW //==0 --> COLLINEAR
double 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);
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);
vector<int> s(N); 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--;
s[++top]=i;
}
ofs<<top+1<<"\n";
for(int i=0;i<=top;i++){
ofs<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
}
}