Pagini recente » Cod sursa (job #273110) | Cod sursa (job #2431405) | Cod sursa (job #428512) | Cod sursa (job #2943296) | Cod sursa (job #3269428)
import java.io.*;
import java.util.*;
public class Main {
public static class MyScanner implements Closeable {
BufferedReader br;
StringTokenizer st;
public MyScanner(String file) throws FileNotFoundException {
br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
@Override
public void close() throws IOException {
br.close();
}
}
public static class Point implements Comparable<Point> {
public double x;
public double y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(Point o) {
if (Double.compare(this.y, o.y) < 0) return -1;
if (Double.compare(this.y, o.y) > 0) return 1;
return Double.compare(this.x, o.x);
}
@Override
public String toString() {
return Double.toString(x) + " " +Double.toString(y);
}
}
public static int ccw(Point p, Point a, Point b) {
double sign = (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x);
// clockwise
// collinear
return Double.compare(sign, 0.0d); // counter-clockwise
}
public static class PolarOrderComparator implements Comparator<Point> {
private Point p;
public PolarOrderComparator(Point p) {
this.p = p;
}
@Override
public int compare(Point p1, Point p2) {
// double dy1 = p1.y - p.y;
// double dy2 = p2.y - p.y;
// double dx1 = p1.x - p.x;
// double dx2 = p2.x - p.x;
//
// if (dy1 >= 0 && dy2 < 0) return -1; // p1 above & p2 below
// else if (dy1 < 0 && dy2 >= 0) return 1; // p1 below & p2 above
// else if (dy1 == 0.0d && dy2 == 0.0d) {
// if (dx1 >= 0 && dx2 < 0) return -1;
// else if (dx1 < 0 && dx2 >= 0) return 1;
// else return 0;
// }
return -ccw(p, p1, p2);
}
}
public static void main(String[] args) throws IOException {
try(MyScanner scanner = new MyScanner("infasuratoare.in");
PrintWriter pw = new PrintWriter(new FileOutputStream("infasuratoare.out"))) {
int N = scanner.nextInt();
Point[] points = new Point[N];
for (int i = 0; i < N; i++) {
points[i] = new Point(scanner.nextDouble(), scanner.nextDouble());
}
Arrays.sort(points);
// Point p = points[1];
//
// for (int i = 2; i <= N; i++) {
// if (points[i].compareTo(p) < 0) {
// p = points[i];
// }
// }
Point p = points[0];
Arrays.sort(points, new PolarOrderComparator(p));
Deque<Point> stack = new ArrayDeque<>();
stack.push(points[0]);
stack.push(points[1]);
for (int i = 2; i < N; i++) {
Point top = stack.pop();
while (stack.size() >= 2 && ccw(stack.peek(), top, points[i]) < 0) {
top = stack.pop(); // go to next one
}
//re-insert last pop because it was ok actually
stack.push(top);
stack.push(points[i]);
}
int convexHullSize = stack.size();
pw.println(convexHullSize);
for (int i = 0; i < convexHullSize; i++) {
pw.println(stack.removeLast());
}
}
}
}