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.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;
- 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 ((b.x-a.x)!=0) {
- return Math.atan((b.y-a.y)/(b.x-a.x));
- } else {
- return Math.asin(1);
- }
- }
- 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 solve() throws NumberFormatException, IOException {
- n=nextInt();
- int m=2;
- points=new Point[n];
- min=Integer.MAX_VALUE;
- minI=0;
- minPoint=new 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].x==min) {
- if (points[i].y<points[minI].y) {
- minI=i;
- }
- }
- if (points[i].x<min) {
- min=points[i].x;
- minI=i;
- }
- }
- minPoint=points[minI];
- Point swap=points[minI];
- points[minI]=points[0];
- points[0]=swap;
- for (int i=0;i<n;i++) {
- points[i].angle=calcAngle(minPoint, points[i]);
- points[i].range=calcRange(minPoint,points[i]);
- }
- points[0].angle=-2;
- Arrays.sort(points);
- for (int i=0;i<n;i++) {
- if (minPoint==points[i]) {
- swap=points[i];
- points[i]=points[0];
- points[0]=swap;
- }
- }
- //points[0]=points[n-1];
- for (int i=3; i<n; i++) {
- while (ccw(points[m-1],points[m],points[i])<=0) {
- m--;
- }
- m++;
- swap=points[m];
- points[m]=points[i];
- points[i]=swap;
- }
- out.println(m+1);
- //out.print(minPoint.x+" "+minPoint.y+"\n");
- for (int i=0; i<m+1;i++) {
- out.print(points[i].x+" "+points[i].y+"\n");
- }
- }
- }
Add Comment
Please, Sign In to add comment