fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3. public final class round_352_c
  4. {
  5.     static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
  6.     static PrintWriter out=new PrintWriter(System.out);
  7. 	static double[] dis1,dis2;
  8. 	static Pair[] tree;
  9.  
  10. 	static double pow(double val1)
  11. 	{
  12. 		return (val1*val1);
  13. 	}
  14.  
  15. 	static double getDis(double x1,double y1,double x2,double y2)
  16. 	{
  17. 		return Math.sqrt(pow(x2-x1)+pow(y2-y1));
  18. 	}
  19.  
  20. 	static void build(int node,int l,int r)
  21. 	{
  22. 		if(l>r)
  23. 		{
  24. 			return;
  25. 		}
  26. 		if(l==r)
  27. 		{
  28. 			tree[node]=new Pair(l,dis2[l]);
  29. 		}
  30. 		else
  31. 		{
  32. 			int mid=(l+r)>>1;
  33. 			build(node<<1,l,mid);
  34. 			build(node<<1|1,mid+1,r);
  35. 			if(tree[node<<1].val<=tree[node<<1|1].val)
  36. 			{
  37. 				tree[node]=new Pair(tree[node<<1].idx,tree[node<<1].val);
  38. 			}
  39. 			else
  40. 			{
  41. 				tree[node]=new Pair(tree[node<<1|1].idx,tree[node<<1|1].val);
  42. 			}
  43. 		}
  44. 	}
  45.  
  46. 	static Pair get(int node,int s,int e,int l,int r)
  47. 	{
  48. 		if(s>e || l>e || r<s)
  49. 		{
  50. 			return new Pair(-1,Double.MAX_VALUE);
  51. 		}
  52. 		if(l<=s && r>=e)
  53. 		{
  54. 			return tree[node];
  55. 		}
  56. 		else
  57. 		{
  58. 			int mid=(s+e)>>1;
  59. 			Pair q1=get(node<<1,s,mid,l,r);
  60. 			Pair q2=get(node<<1|1,mid+1,e,l,r);
  61. 			if(q1.val<=q2.val)
  62. 			{
  63. 				return q1;
  64. 			}
  65. 			else
  66. 			{
  67. 				return q2;
  68. 			}
  69. 		}
  70. 	}
  71.  
  72. 	public static void main(String args[]) throws Exception
  73. 	{
  74. 		double x1=sc.nextDouble(),y1=sc.nextDouble(),x2=sc.nextDouble(),y2=sc.nextDouble(),x3=sc.nextDouble(),y3=sc.nextDouble();
  75. 		double min=Double.MAX_VALUE;
  76. 		int n=sc.nextInt();
  77. 		Node[] a=new Node[n];
  78. 		for(int i=0;i<n;i++)
  79. 		{
  80. 			a[i]=new Node(sc.nextDouble(),sc.nextDouble());
  81. 		}
  82. 		dis1=new double[n];dis2=new double[n];
  83. 		double sum1=0;
  84. 		for(int i=0;i<n;i++)
  85. 		{
  86. 			dis1[i]=getDis(a[i].x1,a[i].y1,x3,y3)+getDis(a[i].x1,a[i].y1,x3,y3);
  87. 			sum1=sum1+dis1[i];
  88. 		}
  89. 		for(int i=0;i<n;i++)
  90. 		{	
  91. 			double curr=getDis(a[i].x1,a[i].y1,x1,y1)+getDis(a[i].x1,a[i].y1,x3,y3);
  92. 			double val1=sum1-dis1[i]+curr;
  93. 			min=Math.min(val1,min);
  94. 			curr=getDis(a[i].x1,a[i].y1,x2,y2)+getDis(a[i].x1,a[i].y1,x3,y3);
  95. 			val1=sum1-dis1[i]+curr;
  96. 			min=Math.min(val1,min);
  97. 		}
  98. 		for(int i=0;i<n;i++)
  99. 		{
  100. 			dis2[i]=getDis(a[i].x1,a[i].y1,x1,y1)+getDis(a[i].x1,a[i].y1,x3,y3);
  101. 		}
  102. 		tree=new Pair[4*n];
  103. 		build(1,0,n-1);
  104. 		for(int i=0;i<n;i++)
  105. 		{
  106. 			double val1=getDis(a[i].x1,a[i].y1,x2,y2)+getDis(a[i].x1,a[i].y1,x3,y3),min_val=Double.MAX_VALUE;
  107. 			int minidx=-1;
  108. 			Pair n1=get(1,0,n-1,0,Math.max(0,i-1)),n2=get(1,0,n-1,Math.min(i+1,n-1),n-1);
  109. 			if(n1.idx!=-1)
  110. 			{
  111. 				if(n1.val<min_val)
  112. 				{
  113. 					min_val=n1.val;
  114. 					minidx=n1.idx;
  115. 				}
  116. 			}
  117. 			if(n2.idx!=-1)
  118. 			{
  119. 				if(n2.val<min_val)
  120. 				{
  121. 					min_val=n2.val;
  122. 					minidx=n2.idx;
  123. 				}
  124. 			}
  125. 			if(min_val<Double.MAX_VALUE)
  126. 			{
  127. 				double curr=sum1-dis1[i]-dis1[minidx]+val1+min_val;
  128. 				min=Math.min(min,curr);
  129. 				//out.println(min);
  130. 			}
  131. 		}
  132. 		out.printf("%.12f\n",min);
  133. 		out.close();
  134. 	}
  135. }
  136. class Node
  137. {
  138. 	double x1,y1;
  139. 	public Node(double x1,double y1)
  140. 	{
  141. 		this.x1=x1;
  142. 		this.y1=y1;
  143. 	}
  144. }
  145. class Pair
  146. {
  147. 	int idx;
  148. 	double val;
  149. 	public Pair(int idx,double val)
  150. 	{
  151. 		this.idx=idx;
  152. 		this.val=val;
  153. 	}
  154. }
  155. class FastScanner
  156. {
  157.     BufferedReader in;
  158.     StringTokenizer st;
  159.  
  160.     public FastScanner(BufferedReader in) {
  161.         this.in = in;
  162.     }
  163.  
  164.     public String nextToken() throws Exception {
  165.         while (st == null || !st.hasMoreTokens()) {
  166.             st = new StringTokenizer(in.readLine());
  167.         }
  168.         return st.nextToken();
  169.     }
  170.  
  171. 	public String next() throws Exception {
  172. 		return nextToken().toString();
  173. 	}
  174.  
  175.     public int nextInt() throws Exception {
  176.         return Integer.parseInt(nextToken());
  177.     }
  178.  
  179.     public long nextLong() throws Exception {
  180.         return Long.parseLong(nextToken());
  181.     }
  182.  
  183.     public double nextDouble() throws Exception {
  184.         return Double.parseDouble(nextToken());
  185.     }
  186. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:3: error: class round_352_c is public, should be declared in a file named round_352_c.java
public final class round_352_c
             ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/GLxs4H
language:
Java (12.0.1)
created:
8 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!