Cod sursa(job #1898545)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 2 martie 2017 09:23:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.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;
    int m=1;
    for (int i=1;i<N;i++){
		while (i<N-1 && direct(sr,A[i],A[i+1])==0)i++;
		
		A[m]=A[i];
		m++;
	}
	N=m;
    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;
     
}














/*#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point{
	int x,y;
	
}A[121000],sr;
int N;

void read(){
	fin >>N:
	for (int i=1;i<=N;i++) if ()
}

int main(){
	
	
	return 0;
	
}
* 
* */