Pagini recente » Cod sursa (job #661046) | Cod sursa (job #443158) | Cod sursa (job #2955821) | Cod sursa (job #1228012) | Cod sursa (job #1827816)
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, 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;
}
}