fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cmath>
  4. #include <vector>
  5. using namespace std;
  6. long long INF = 9876543212345;
  7. long long ans;
  8. int n;
  9.  
  10. struct Point{
  11.     int x;
  12.     int y;
  13.     Point(){
  14.         x=0;y=0;
  15.     }
  16.     Point operator + (Point p){
  17.         Point ans;
  18.         ans.x = x + p.x;
  19.         ans.y = y + p.y;
  20.         return ans;
  21.     }
  22.  
  23.     Point operator - (Point p){
  24.         Point ans;
  25.         ans.x = x-p.x;
  26.         ans.y = y-p.y;
  27.         return ans;
  28.     }
  29.     long long scalar(){
  30.         return (long long)x*x+(long long)y*y;
  31.     }
  32. };
  33. Point point[22];
  34.  
  35. void dfs(int i,Point p,int cnt){
  36.     if(!cnt){
  37.         for(int j=i+1;j<=n;++j)p = p-point[j];
  38.     	ans = min(ans,p.scalar());
  39.     	return;
  40.     }
  41.     if(i==n) return;
  42.     for(int j=i+1;j<=n;++j){
  43.        	p = p+point[j];
  44.         dfs(j,p,cnt-1);
  45.         p = p-point[j]-point[j];
  46.     }
  47. } 
  48. int main(){
  49.     int t;	
  50.     for(scanf("%d",&t);t;--t){
  51.         Point p;
  52.         ans=INF;
  53.         scanf("%d",&n);
  54.         for(int i=1;i<=n;++i){
  55.             scanf("%d%d",&point[i].x,&point[i].y);
  56.         }
  57.         dfs(0,p,n>>1);
  58.         printf("%.6lf\n",sqrt(ans));
  59.     }
  60. }
  61.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000
stdout
copy 
0.000000
282842.712475
https://ideone.com/ctYs2L
BOJ 1007
language:
C++14 (gcc 8.3)
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!