Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintWriter;
- import java.util.StringTokenizer;
- import java.util.ArrayList;
- import java.lang.Math;
- import java.util.Arrays;
- public class grMain implements Runnable {
- StringTokenizer st;
- BufferedReader in;
- PrintWriter out;
- public static class Point implements Comparable {
- int x;
- int y;
- int num;
- double angle;
- int range;
- public int compareTo(Object other) {
- Point vertex = (Point) other;
- if (angle - vertex.angle>0) {
- return -1;
- }
- if (angle - vertex.angle<0) {
- return 1;
- }
- if ((angle - vertex.angle)==0) {
- return -(range-vertex.range);
- }
- return 0;
- }
- Point () {
- }
- Point (int a) {
- num=a;
- }
- }
- //variables
- Point points[];
- int n;
- int min;
- int minI;
- Point minPoint;
- ArrayList <Point> stack;
- int calcRange(Point a, Point b) {
- return (a.x-b.y)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
- }
- double calcAngle(Point a, Point b) {
- if (Math.atan2(b.x-a.x,b.y-a.y)>0) {
- return Math.atan2(b.x-a.x,b.y-a.y);
- } else {
- return Math.atan2(b.x-a.x,b.y-a.y)+2*Math.PI;
- }
- }
- public static void main(String[] args) {
- new Thread(new grMain()).run();
- }
- public void run() {
- try {
- in = new BufferedReader(new FileReader("hull.in"));
- out = new PrintWriter(new FileWriter("hull.out"));
- solve();
- } catch (Exception e) {
- e.printStackTrace();
- } finally {
- out.flush();
- out.close();
- }
- }
- String nextToken() throws IOException {
- while (st == null || !st.hasMoreTokens()) {
- st = new StringTokenizer(in.readLine());
- }
- return st.nextToken();
- }
- int nextInt() throws NumberFormatException, IOException {
- return Integer.parseInt(nextToken());
- }
- long nextLong() throws NumberFormatException, IOException {
- return Long.parseLong(nextToken());
- }
- double nextDouble() throws NumberFormatException, IOException {
- return Double.parseDouble(nextToken());
- }
- int ccw(Point p1, Point p2, Point p3){
- return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
- }
- void pop(){
- stack.remove(stack.size()-1);
- }
- Point Top () {
- return stack.get(stack.size()-1);
- }
- Point NexttoTop (){
- return stack.get(stack.size()-2);
- }
- @SuppressWarnings("unchecked")
- void solve() throws NumberFormatException, IOException {
- n=nextInt();
- int m=2;
- points=new Point[n];
- min=Integer.MAX_VALUE;
- minI=0;
- minPoint=new Point();
- stack = new ArrayList<Point>();
- for (int i=0; i<n; i++) {
- points[i]= new Point(i);
- }
- for (int i=0; i<n;i++) {
- points[i].x=nextInt();
- points[i].y=nextInt();
- if (points[i].y==min) {
- if (points[i].x<points[minI].x) {
- minI=i;
- }
- }
- if (points[i].y<min) {
- min=points[i].y;
- minI=i;
- }
- }
- minPoint=points[minI];
- Point swap=points[minI];
- points[minI]=points[1];
- points[1]=swap;
- for (int i=0;i<n;i++) {
- points[i].angle=calcAngle(minPoint, points[i]);
- points[i].range=calcRange(minPoint,points[i]);
- }
- points[1].angle=-2;
- Arrays.sort(points);
- for (int i=0;i<n;i++) {
- if (minPoint==points[i]) {
- swap=points[i];
- points[i]=points[1];
- points[1]=swap;
- }
- }
- points[0]=points[n-1];
- for (int i=2; i<n; i++) {
- while (ccw(NexttoTop(),Top(),points[i])<=0) {
- pop();
- }
- stack.add(points[i]);
- }
- int s=stack.size();
- out.println(s);
- for (int i=0; i<s;i++) {
- out.print(stack.get(i).x+" "+stack.get(i).y+"\n");
- }
- }
- }
Add Comment
Please, Sign In to add comment