Pagini recente » Cod sursa (job #350642) | Cod sursa (job #2973660) | Cod sursa (job #2527459) | Cod sursa (job #494197) | Cod sursa (job #3269426)
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+1];
for (int i = 1; i <= N; i++) {
points[i] = new Point(scanner.nextDouble(), scanner.nextDouble());
}
Point p = points[1];
for (int i = 2; i <= N; i++) {
if (points[i].compareTo(p) < 0) {
p = points[i];
}
}
Arrays.sort(points, 1, N+1, new PolarOrderComparator(p));
Deque<Point> stack = new LinkedList<>();
stack.push(points[1]);
stack.push(points[2]);
for (int i = 3; i <= N; i++) {
Point top = stack.pop();
while (!stack.isEmpty() && 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());
}
}
}
}