fork download
copy 
  1. // TPoint.java
  2.  
  3. package convexHull;
  4.  
  5. public class TPoint {
  6. private int x;
  7. private int y;
  8. public TPoint()
  9. {
  10. 	x = 0;
  11. 	y = 0;
  12. }
  13. public TPoint(int x, int y) {
  14. 	super();
  15. 	this.x = x;
  16. 	this.y = y;
  17. }
  18.  
  19. public int getX() {
  20. 	return x;
  21. }
  22. public void setX(int x) {
  23. 	this.x = x;
  24. }
  25. public int getY() {
  26. 	return y;
  27. }
  28. public void setY(int y) {
  29. 	this.y = y;
  30. }
  31.  
  32. }
  33.  
  34. // Jarvis.java
  35.  
  36. package convexHull;
  37.  
  38. import java.util.ArrayList;
  39.  
  40. public class Jarvis {
  41. 	public static int vect(TPoint a1,TPoint a2,TPoint b1,TPoint b2)
  42. 	{
  43. 		return (a2.getX()-a1.getX())*(b2.getY()-b1.getY())-(b2.getX()-b1.getX())*(a2.getY()-a1.getY());
  44. 	}
  45. 	public static int dist2(TPoint a1,TPoint a2)
  46. 	{
  47. 		return (a2.getX()-a1.getX())*(a2.getX()-a1.getX())+(a2.getY()-a1.getY())*(a2.getY()-a1.getY());
  48. 	}
  49. 	public static void Solve(ArrayList<TPoint> a,ArrayList<TPoint> b)
  50. 	{
  51. 		int i,j,k,m,n,min;
  52. 		n = a.size();
  53. 		m = 0;
  54. 		try
  55. 		{
  56. 		for(i = 1;i < n;i++)
  57. 			if(a.get(i).getY() < a.get(m).getY())
  58. 				m = i;
  59. 			else if(a.get(i).getY() == a.get(m).getY() && a.get(i).getX() > a.get(m).getX())
  60. 				m = i;
  61. 		b.add(a.get(m));
  62. 		a.set(m, a.get(0));
  63. 		a.set(0, b.get(0));
  64. 		k = 0;
  65. 		min = 1;
  66. 		do
  67. 		{
  68. 			for(j = 1;j < n;j++)
  69. 				if(vect(b.get(k),a.get(min),b.get(k),a.get(j)) < 0 || 
  70. 						vect(b.get(k),a.get(min),b.get(k),a.get(j)) == 0 &&
  71. 						dist2(b.get(k),a.get(min)) < dist2(b.get(k),a.get(j)))
  72. 					min = j;
  73. 			k++;
  74. 			b.add(a.get(min));
  75. 			min = 0;
  76. 		}
  77. 		while(b.get(k).getX() != b.get(0).getX() || b.get(k).getY() != b.get(0).getY());
  78. 		}
  79. 		catch(IndexOutOfBoundsException ex)
  80. 		{
  81.  
  82. 		}
  83. 	}
  84. }
  85.  
  86. // Graham.java
  87.  
  88. package convexHull;
  89.  
  90. import java.util.ArrayList;
  91.  
  92. public class Graham {
  93. 	public static int direction(TPoint p0,TPoint p1,TPoint p2)
  94. 	{
  95. 		return (p1.getX()-p0.getX())*(p2.getY()-p0.getY())-(p2.getX()-p0.getX())*(p1.getY()-p0.getY());
  96. 	}
  97. 	public static int distSquared(TPoint a,TPoint b)
  98. 	{
  99. 		return (a.getX() - b.getX())*(a.getX() - b.getX())+(a.getY()-b.getY())*(a.getY()-b.getY());
  100. 	}
  101. 	public static boolean comp(TPoint p0,TPoint a,TPoint b)
  102. 	{
  103. 		int d = direction(p0,a,b);
  104. 		if(d != 0)
  105. 			return d>0;
  106. 		else
  107. 			return distSquared(p0,a) > distSquared(p0,b); 
  108. 	}
  109. 	public static void heapify(int l,int r,ArrayList<TPoint> A)
  110. 	{
  111. 		int i,j;
  112. 		TPoint x;
  113. 		boolean isCorrect;
  114. 		x = A.get(l);
  115. 		i = l;
  116. 		j = 2 * i;
  117. 		isCorrect = false;
  118. 		while(j <= r && !isCorrect)
  119. 		{
  120. 			if(j < r && comp(A.get(0),A.get(j),A.get(j+1)))
  121. 				j++;
  122. 			if(comp(A.get(0),x,A.get(j)))
  123. 			{
  124. 				A.set(i, A.get(j));
  125. 				i = j;
  126. 				j = 2 * i;
  127. 			}
  128. 			else
  129. 				isCorrect = true;
  130. 		}
  131. 		A.set(i, x);
  132. 	}
  133. 	public static void buildHeap(ArrayList<TPoint> A)
  134. 	{
  135. 		int n;
  136. 		n = A.size()-1;
  137. 		for(int i = n/2;i >= 1;i--)
  138. 			heapify(i,n,A);
  139. 	}
  140. 	public static void heapSort(ArrayList<TPoint> A)
  141. 	{
  142. 		TPoint x;
  143. 		int n = A.size()-1;
  144. 		buildHeap(A);
  145. 		for(int i = n;i >= 2;i--)
  146. 		{
  147. 			x = A.get(1);
  148. 			A.set(1, A.get(i));
  149. 			A.set(i, x);
  150. 			heapify(1,i - 1,A);
  151. 		}
  152. 	}
  153. 	public static int removeDup(ArrayList<TPoint> A,ArrayList<TPoint> B)
  154. 	{
  155. 		int i,prev,count,size;
  156. 		size = A.size();
  157. 		prev = 1;
  158. 		for(i = 1; i < size;i++)
  159. 		{
  160. 			if(direction(A.get(0),A.get(i),A.get(prev))!=0)
  161. 			{
  162. 				prev++;
  163. 				B.add(A.get(prev));
  164. 				A.set(prev, A.get(i));
  165. 			}	
  166. 		}
  167. 		i = prev + 1;
  168. 		try
  169. 		{
  170. 			while(!B.isEmpty())
  171. 			{
  172. 				System.out.println(i+" "+size);
  173. 				A.set(i, B.get(0));
  174. 				B.remove(0);
  175. 				i++;
  176. 			}
  177. 			System.out.println();
  178. 			}
  179. 			catch(IndexOutOfBoundsException ex)
  180. 			{
  181.  
  182. 			}
  183. 		count = prev + 1;
  184. 		return count;
  185. 	}
  186. 	public static void Solve(ArrayList<TPoint> P,ArrayList<TPoint> S)
  187. 	{
  188. 		int j,m,n,min,top;
  189. 		TPoint temp;
  190. 		n = P.size();
  191. 		min = 0;
  192. 		for(int i = 1;i < n;i++)
  193. 			if(P.get(i).getY() < P.get(min).getY() || (P.get(i).getY() == P.get(min).getY() && P.get(i).getX() < P.get(min).getX()))
  194. 				min = i;
  195. 		temp = P.get(0);
  196. 		P.set(0, P.get(min));
  197. 		P.set(min, temp);
  198. 		heapSort(P);
  199. 		while(!S.isEmpty())
  200. 			S.remove(0);
  201. 		m = removeDup(P,S);
  202. 		while(!S.isEmpty())
  203. 			S.remove(0);
  204. 		top = -1;
  205. 		try
  206. 		{
  207. 		top++;
  208. 		S.add(top,P.get(0));
  209. 		top++;
  210. 		S.add(top,P.get(1));
  211. 		top++;
  212. 		S.add(top,P.get(2));
  213. 		for(int i = 3;i < m;i++)
  214. 		{
  215. 			while(direction(S.get(top-1),S.get(top),P.get(i))<=0)
  216. 			{
  217. 				S.remove(top);
  218. 				top--;
  219. 			}
  220. 			top++;
  221. 			S.add(P.get(i));
  222. 		}
  223. 		S.add(P.get(0));
  224. 		}
  225. 		catch(IndexOutOfBoundsException ex)
  226. 		{
  227.  
  228. 		}
  229. 	}
  230. }
  231.  
  232. // ConvexHull.java
  233.  
  234. package convexHull;
  235.  
  236. import java.awt.Canvas;
  237. import java.awt.Graphics;
  238. import java.awt.event.MouseEvent;
  239. import java.awt.event.MouseListener;
  240. import java.util.ArrayList;
  241.  
  242. import javax.swing.JFrame;
  243.  
  244. public class ConvexHull extends Canvas implements MouseListener{
  245. 	private static int countA;
  246. 	private static int countB;
  247. 	private static ArrayList<TPoint> A = new ArrayList<TPoint>();
  248. 	private static ArrayList<TPoint> B = new ArrayList<TPoint>();
  249. 	private static Graphics gDC;
  250. 	public ConvexHull() {
  251. 		// TODO Auto-generated constructor stub
  252. 		countA = 0;
  253. 		countB = 0;
  254. 		addMouseListener((MouseListener) this);
  255. 	}
  256.  
  257. 	public static void main(String[] args) {
  258. 		// TODO Auto-generated method stub
  259. 		JFrame jf = new JFrame("Convex Hull");
  260. 		ConvexHull convexHull = new ConvexHull();
  261. 		jf.setSize(800, 600);
  262. 		jf.setVisible(true);
  263. 		jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  264. 		jf.add(convexHull);
  265. 	}
  266.  
  267. 	public void paint(Graphics gDC)
  268. 	{
  269. 		for(int i = 0;i < countA;i++)
  270. 			gDC.fillOval(A.get(i).getX()-5, A.get(i).getY()-5, 10, 10);
  271. 		for(int i = 0;i < countB;i++)
  272. 		{
  273. 			gDC.drawLine(B.get(i).getX(),B.get(i).getY(), B.get((i+1)%countB).getX(),B.get((i+1)%countB).getY());
  274. 			System.out.println(B.get(i).getX() + " "+ B.get(i).getY());
  275. 		}
  276. 		System.out.println();	
  277. 	}
  278.  
  279. 	@Override
  280. 	public void mouseClicked(MouseEvent e) {
  281. 		// TODO Auto-generated method stub
  282.  
  283. 	}
  284.  
  285. 	@Override
  286. 	public void mouseEntered(MouseEvent e) {
  287. 		// TODO Auto-generated method stub
  288.  
  289. 	}
  290.  
  291. 	@Override
  292. 	public void mouseExited(MouseEvent e) {
  293. 		// TODO Auto-generated method stub
  294.  
  295. 	}
  296.  
  297. 	@Override
  298. 	public void mousePressed(MouseEvent e) {
  299. 		// TODO Auto-generated method stub
  300. 		int x = e.getX();
  301. 		int y = e.getY();
  302. 		TPoint point = new TPoint(x,y);
  303. 		A.add(point);
  304. 		countA++;
  305. 		while(!B.isEmpty())
  306. 			B.remove(B.get(0));
  307. 		//Jarvis.Solve(A, B);
  308. 		Graham.Solve(A, B);
  309. 		countB = B.size();
  310. 		repaint();
  311. 	}
  312.  
  313. 	@Override
  314. 	public void mouseReleased(MouseEvent e) {
  315. 		// TODO Auto-generated method stub
  316.  
  317. 	}
  318.  
  319. }
  320.  
  321.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:36: error: class, interface, or enum expected
package convexHull;
^
Main.java:38: error: class, interface, or enum expected
import java.util.ArrayList;
^
Main.java:88: error: class, interface, or enum expected
package convexHull;
^
Main.java:90: error: class, interface, or enum expected
import java.util.ArrayList;
^
Main.java:234: error: class, interface, or enum expected
package convexHull;
^
Main.java:236: error: class, interface, or enum expected
import java.awt.Canvas;
^
Main.java:237: error: class, interface, or enum expected
import java.awt.Graphics;
^
Main.java:238: error: class, interface, or enum expected
import java.awt.event.MouseEvent;
^
Main.java:239: error: class, interface, or enum expected
import java.awt.event.MouseListener;
^
Main.java:240: error: class, interface, or enum expected
import java.util.ArrayList;
^
Main.java:242: error: class, interface, or enum expected
import javax.swing.JFrame;
^
11 errors
stdout
copy 
Standard output is empty
https://ideone.com/uH8g0a
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

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!