Cod sursa(job #1827815)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 12 decembrie 2016 13:21:05
Problema Infasuratoare convexa Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 2.87 kb

import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;

class Punct {
	
	public double x;
	public double y;
	
	Punct() {
		this.x = 0;
		this.y = 0;
	}
	
	Punct(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
}

public class Main {
	
	static ArrayList<Punct> a = new ArrayList<>();
	static Punct px = new Punct();
    static boolean PrimescPuncte = true;
    static ArrayList<Punct> s = new ArrayList<>();
	
    static double delta(Punct p, Punct q, Punct r) {
        double x = (q.x - p.x) * (r.y - p.y) - (r.x - p.x) * (q.y - p.y);
        return x;
    }
	 
	
    static void solve() {

        int k = 0;  
        for (int i = 1; i < a.size(); ++i) {
            if (a.get(k).x > a.get(i).x) {
                k = i;
            } else if (a.get(k).x == a.get(i).x && a.get(k).y > a.get(i).y) {
                k = i;
            }
        }

        Punct paux = new Punct();
        paux.x = a.get(0).x;
        paux.y = a.get(0).y;
        a.get(0).x = a.get(k).x;
        a.get(0).y = a.get(k).y;
        a.get(k).x = paux.x;
        a.get(k).y = paux.y;

        px.x = a.get(0).x;
        px.y = a.get(0).y;

        Comparator compare = new PunctComparator();
        Collections.sort(a.subList(1, a.size()), compare);

        
        s.add(a.get(0));
        s.add(a.get(1));

        for (int i = 2; i < a.size(); ++i) {
            int sz = s.size();
            px.x = a.get(i).x;
            px.y = a.get(i).y;
            if (sz >= 2 && delta(s.get(sz - 2), s.get(sz - 1), px) > 0) {    // viraj
                while (sz >= 2 && delta(s.get(sz - 2), s.get(sz - 1), px) > 0) {
                    s.remove(s.size() - 1);
                    sz = s.size();
                }
            }
            s.add(a.get(i));
        }
           
    }
    
    public static void main(String[] args) throws IOException {
    	
    	Scanner in = new Scanner(new FileReader("infasuratoare.in")).useLocale(Locale.US);
    	BufferedWriter out = new BufferedWriter(new FileWriter("infasuratoare.out"));
    	
    	int n = in.nextInt();
    	for (int i = 0; i < n; ++i) {
			Punct Po = new Punct();
			Po.x = in.nextDouble();
			Po.y = in.nextDouble();
			a.add(Po);
    	}
    	
    	solve();
    	
    	out.write(Integer.toString(s.size()) + '\n');
    	for (int i = s.size() - 1; i >= 0; --i) {
        	out.write(Double.toString(s.get(i).x) + " " + Double.toString(s.get(i).y) + '\n');
    	}
    	
    	in.close();
    	out.close();
    }
}

class PunctComparator implements Comparator<Punct>
{
    @Override
    public int compare(Punct a, Punct b) {
        double d = Main.delta(Main.px, a, b);
        if (d > 0) {
            return 1;
        } else if (d < 0) {
        	return -1;
        }
        return 0;
    }
}