fork download
copy 
  1. //package com.icpc.year2016.chennaionsite;
  2.  
  3. import java.io.*;
  4. import java.util.*;
  5.  
  6. class TaskB
  7. {
  8.     public static void main(String[] args)
  9.     {
  10.         InputReader in = new InputReader(System.in);
  11.         OutputWriter out = new OutputWriter(System.out);
  12. 		Solver solver = new Solver(in, out);
  13.  
  14. 		solver.solve();
  15.         in.close();
  16.         out.flush();
  17.         out.close();
  18.     }
  19.  
  20.     static class Solver
  21.     {
  22.         int n;
  23.         Point[] points;
  24.         InputReader in;
  25.         OutputWriter out;
  26.  
  27. 		void solve()
  28. 		{
  29. 			n = in.nextInt();
  30. 			points = new Point[n];
  31.  
  32. 			for (int i = 0; i < n; i++)
  33. 				points[i] = new Point(in.nextLong(), in.nextLong(), in.nextLong());
  34.  
  35. 			long cost = 0;
  36.  
  37. 			for (Point p : getConvexHull())
  38. 				cost += p.cost;
  39.  
  40. 			out.println(cost);
  41. 		}
  42.  
  43. 		Stack<Point> getConvexHull()
  44. 		{
  45. 			Stack<Point> hull = new Stack<>();
  46.  
  47. 			Arrays.sort(points, new Comparator<Point>()
  48. 			{
  49. 				@Override public int compare(Point o1, Point o2)
  50. 				{
  51. 					return Long.compare(o1.y, o2.y);
  52. 				}
  53. 			});
  54.  
  55. 			for (int i = 1; i < n; i++)
  56. 				points[i].polarAngle = points[0].findPolarAngle(points[i]);
  57.  
  58. 			Arrays.sort(points, 1, n, new Comparator<Point>()
  59. 			{
  60. 				@Override public int compare(Point o1, Point o2)
  61. 				{
  62. 					return Double.compare(o1.polarAngle, o2.polarAngle);
  63. 				}
  64. 			});
  65.  
  66. /*			System.out.println("pts :");
  67.  
  68. 			for (int i = 0; i < n; i++)
  69. 				System.out.println("i : " + i + ", pt : " + points[i]);
  70.  
  71. 			System.out.println("hull : " + hull);*/
  72.  
  73. 			hull.push(points[0]);
  74.  
  75. 			int ctr = 1;
  76.  
  77. 			while (ctr < n && points[0].equals(points[ctr]))
  78. 				ctr++;
  79.  
  80. 			if (ctr == n)
  81. 				return hull;
  82.  
  83. 			int ctr2 = ctr + 1;
  84.  
  85. 			while (ctr2 < n && counterClockWise(points[0], points[ctr], points[ctr2]) == 0)
  86. 				ctr2++;
  87.  
  88. 			hull.push(points[ctr2 - 1]);
  89.  
  90. 			for (int i = ctr2; i < n; i++)
  91. 			{
  92. 				Point top = hull.pop();
  93.  
  94. 				while (counterClockWise(hull.peek(), top, points[i]) <= 0)
  95. 				{
  96. //					System.out.println("\thull : " + hull);
  97. 					top = hull.pop();
  98. 				}
  99.  
  100. 				hull.push(top);
  101. 				hull.push(points[i]);
  102. 			}
  103.  
  104. 			return hull;
  105. 		}
  106.  
  107. 		int counterClockWise(Point a, Point b, Point c)
  108. 		{
  109. 			long xx = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  110.  
  111. 			if (xx < 0)
  112. 				return -1;
  113. 			else if (xx > 0)
  114. 				return 1;
  115.  
  116. 			return 0;
  117. 		}
  118.  
  119. 		static class Point
  120. 		{
  121. 			long x, y, cost;
  122. 			double polarAngle;
  123.  
  124. 			double findPolarAngle(Point a)
  125. 			{
  126. 				return Math.atan2(a.y - y, a.x - x) * 180.0 / Math.PI;
  127. 			}
  128.  
  129. 			Point(long x, long y, long cost)
  130. 			{
  131. 				this.x = x;
  132. 				this.y = y;
  133. 				this.cost = cost;
  134. 			}
  135.  
  136. 			@Override public boolean equals(Object obj)
  137. 			{
  138. 				Point pt = (Point) obj;
  139.  
  140. 				return x == pt.x && y == pt.y;
  141. 			}
  142.  
  143. 			@Override public String toString()
  144. 			{
  145. 				return "(" + x + ", " + y + ") => " + cost;
  146. 			}
  147.  
  148. 		}
  149.  
  150.         public Solver(InputReader in, OutputWriter out)
  151.         {
  152.         	this.in = in;
  153.         	this.out = out;
  154.         }
  155.  
  156. 	}
  157.  
  158.     static class InputReader
  159.     {
  160.         private InputStream stream;
  161.         private byte[] buf = new byte[1024];
  162.         private int curChar;
  163.         private int numChars;
  164.  
  165.         public InputReader(InputStream stream)
  166.         {
  167.             this.stream = stream;
  168.         }
  169.  
  170.         public int read()
  171.         {
  172.             if (numChars == -1)
  173.                 throw new InputMismatchException();
  174.  
  175.             if (curChar >= numChars)
  176.             {
  177.                 curChar = 0;
  178.                 try
  179.                 {
  180.                     numChars = stream.read(buf);
  181.                 } catch (IOException e)
  182.                 {
  183.                     throw new InputMismatchException();
  184.                 }
  185.                 if (numChars <= 0)
  186.                     return -1;
  187.             }
  188.  
  189.             return buf[curChar++];
  190.         }
  191.  
  192.         public int nextInt()
  193.         {
  194.             int c = read();
  195.  
  196.             while (isSpaceChar(c))
  197.                 c = read();
  198.  
  199.             int sgn = 1;
  200.  
  201.             if (c == '-')
  202.             {
  203.                 sgn = -1;
  204.                 c = read();
  205.             }
  206.  
  207.             int res = 0;
  208.  
  209.             do
  210.             {
  211.                 if (c < '0' || c > '9')
  212.                     throw new InputMismatchException();
  213.  
  214.                 res *= 10;
  215.                 res += c & 15;
  216.  
  217.                 c = read();
  218.             } while (!isSpaceChar(c));
  219.  
  220.             return res * sgn;
  221.         }
  222.  
  223.         public int[] nextIntArray(int arraySize)
  224.         {
  225.             int array[] = new int[arraySize];
  226.  
  227.             for (int i = 0; i < arraySize; i++)
  228.                 array[i] = nextInt();
  229.  
  230.             return array;
  231.         }
  232.  
  233.         public long nextLong()
  234.         {
  235.             int c = read();
  236.  
  237.             while (isSpaceChar(c))
  238.                 c = read();
  239.  
  240.             int sign = 1;
  241.  
  242.             if (c == '-')
  243.             {
  244.                 sign = -1;
  245.  
  246.                 c = read();
  247.             }
  248.  
  249.             long result = 0;
  250.  
  251.             do
  252.             {
  253.                 if (c < '0' || c > '9')
  254.                     throw new InputMismatchException();
  255.  
  256.                 result *= 10;
  257.                 result += c & 15;
  258.  
  259.                 c = read();
  260.             } while (!isSpaceChar(c));
  261.  
  262.             return result * sign;
  263.         }
  264.  
  265.         public long[] nextLongArray(int arraySize)
  266.         {
  267.             long array[] = new long[arraySize];
  268.  
  269.             for (int i = 0; i < arraySize; i++)
  270.                 array[i] = nextLong();
  271.  
  272.             return array;
  273.         }
  274.  
  275.         public float nextFloat()
  276.         {
  277.             float result, div;
  278.             byte c;
  279.  
  280.             result = 0;
  281.             div = 1;
  282.             c = (byte) read();
  283.  
  284.             while (c <= ' ')
  285.                 c = (byte) read();
  286.  
  287.             boolean isNegative = (c == '-');
  288.  
  289.             if (isNegative)
  290.                 c = (byte) read();
  291.  
  292.             do
  293.             {
  294.                 result = result * 10 + c - '0';
  295.             } while ((c = (byte) read()) >= '0' && c <= '9');
  296.  
  297.             if (c == '.')
  298.                 while ((c = (byte) read()) >= '0' && c <= '9')
  299.                     result += (c - '0') / (div *= 10);
  300.  
  301.             if (isNegative)
  302.                 return -result;
  303.  
  304.             return result;
  305.         }
  306.  
  307.         public double nextDouble()
  308.         {
  309.             double ret = 0, div = 1;
  310.             byte c = (byte) read();
  311.  
  312.             while (c <= ' ')
  313.                 c = (byte) read();
  314.  
  315.             boolean neg = (c == '-');
  316.  
  317.             if (neg)
  318.                 c = (byte) read();
  319.  
  320.             do
  321.             {
  322.                 ret = ret * 10 + c - '0';
  323.             } while ((c = (byte) read()) >= '0' && c <= '9');
  324.  
  325.             if (c == '.')
  326.                 while ((c = (byte) read()) >= '0' && c <= '9')
  327.                     ret += (c - '0') / (div *= 10);
  328.  
  329.             if (neg)
  330.                 return -ret;
  331.  
  332.             return ret;
  333.         }
  334.  
  335.         public String next()
  336.         {
  337.             int c = read();
  338.  
  339.             while (isSpaceChar(c))
  340.                 c = read();
  341.  
  342.             StringBuilder res = new StringBuilder();
  343.  
  344.             do
  345.             {
  346.                 res.appendCodePoint(c);
  347.  
  348.                 c = read();
  349.             } while (!isSpaceChar(c));
  350.  
  351.             return res.toString();
  352.         }
  353.  
  354.         public boolean isSpaceChar(int c)
  355.         {
  356.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  357.         }
  358.  
  359.         public String nextLine()
  360.         {
  361.             int c = read();
  362.  
  363.             StringBuilder result = new StringBuilder();
  364.  
  365.             do
  366.             {
  367.                 result.appendCodePoint(c);
  368.  
  369.                 c = read();
  370.             } while (!isNewLine(c));
  371.  
  372.             return result.toString();
  373.         }
  374.  
  375.         public boolean isNewLine(int c)
  376.         {
  377.             return c == '\n';
  378.         }
  379.  
  380.         public void close()
  381.         {
  382.             try
  383.             {
  384.                 stream.close();
  385.             } catch (IOException e)
  386.             {
  387.                 e.printStackTrace();
  388.             }
  389.         }
  390.  
  391.     }
  392.  
  393.     static class OutputWriter
  394.     {
  395.         private PrintWriter writer;
  396.  
  397.         public OutputWriter(OutputStream stream)
  398.         {
  399.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
  400.                     stream)));
  401.         }
  402.  
  403.         public OutputWriter(Writer writer)
  404.         {
  405.             this.writer = new PrintWriter(writer);
  406.         }
  407.  
  408.         public void println(int x)
  409.         {
  410.             writer.println(x);
  411.         }
  412.  
  413.         public void print(int x)
  414.         {
  415.             writer.print(x);
  416.         }
  417.  
  418. 		public void println(char x)
  419. 		{
  420. 			writer.println(x);
  421. 		}
  422.  
  423. 		public void print(char x)
  424. 		{
  425. 			writer.print(x);
  426. 		}
  427.  
  428.         public void println(int array[], int size)
  429.         {
  430.             for (int i = 0; i < size; i++)
  431.                 println(array[i]);
  432.         }
  433.  
  434.         public void print(int array[], int size)
  435.         {
  436.             for (int i = 0; i < size; i++)
  437.                 print(array[i] + " ");
  438.         }
  439.  
  440.         public void println(long x)
  441.         {
  442.             writer.println(x);
  443.         }
  444.  
  445.         public void print(long x)
  446.         {
  447.             writer.print(x);
  448.         }
  449.  
  450.         public void println(long array[], int size)
  451.         {
  452.             for (int i = 0; i < size; i++)
  453.                 println(array[i]);
  454.         }
  455.  
  456.         public void print(long array[], int size)
  457.         {
  458.             for (int i = 0; i < size; i++)
  459.                 print(array[i]);
  460.         }
  461.  
  462.         public void println(float num)
  463.         {
  464.             writer.println(num);
  465.         }
  466.  
  467.         public void print(float num)
  468.         {
  469.             writer.print(num);
  470.         }
  471.  
  472.         public void println(double num)
  473.         {
  474.             writer.println(num);
  475.         }
  476.  
  477.         public void print(double num)
  478.         {
  479.             writer.print(num);
  480.         }
  481.  
  482.         public void println(String s)
  483.         {
  484.             writer.println(s);
  485.         }
  486.  
  487.         public void print(String s)
  488.         {
  489.             writer.print(s);
  490.         }
  491.  
  492.         public void println()
  493.         {
  494.             writer.println();
  495.         }
  496.  
  497.         public void printSpace()
  498.         {
  499.             writer.print(" ");
  500.         }
  501.  
  502. 		public void printf(String format, Object args)
  503. 		{
  504. 			writer.printf(format, args);
  505. 		}
  506.  
  507.         public void flush()
  508.         {
  509.             writer.flush();
  510.         }
  511.  
  512.         public void close()
  513.         {
  514.             writer.close();
  515.         }
  516.  
  517.     }
  518.  
  519. }
Runtime error #stdin #stdout #stderr 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at TaskB$InputReader.read(Main.java:173)
	at TaskB$InputReader.nextInt(Main.java:197)
	at TaskB$Solver.solve(Main.java:29)
	at TaskB.main(Main.java:14)
https://ideone.com/VQe6nC
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!