Назад к лучшим решениям Status: AC, problem ZELC, contest ZEL07. By smylic (Pavel Irzhavski), 2007-02-22 15:10:50.
  1. #include <stdio.h>
  2. #include <memory.h>
  3. #include <math.h>
  4.  
  5. const int maxn = 3100;
  6.  
  7. double x[2*maxn], y[2*maxn];
  8. int n, m;
  9.  
  10. double r[maxn];
  11.  
  12. int p[maxn];
  13. bool w[maxn];
  14.  
  15. inline double sqr(double x)
  16. {
  17.     return x*x;
  18. }
  19.  
  20. inline double dist(int i, int j)
  21. {
  22.     return sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
  23. }
  24.  
  25. inline double cos_angle(int i, int j, int k, double a, double b)
  26. {
  27.     return ((x[i]-x[j])*(x[i]-x[k])+(y[i]-y[j])*(y[i]-y[k]))/a/b;
  28. }
  29.  
  30. inline bool optimize(int i, int j, int k)
  31. {
  32.     double a = dist(i, j);
  33.     double b = dist(j, k);
  34.     double c = dist(k, i);
  35.     double aa = cos_angle(i, j, k, a, c);
  36.     double bb = cos_angle(j, k, i, b, a);
  37.     double cc = cos_angle(k, i, j, c, b);
  38.     if (aa <= -0.5 || bb <= -0.5 || cc <= -0.5)
  39.         return false;
  40.     double p, q;
  41.     p = (x[i]+x[j])/2 + (y[j]-y[i])*sqrt(3.0)/2;
  42.     q = (y[i]+y[j])/2 + (x[i]-x[j])*sqrt(3.0)/2;
  43.     if ((p*(y[j]-y[i]) + q*(x[i]-x[j]) + (x[j]*y[i] - x[i]*y[j])) * 
  44.         (x[k]*(y[j]-y[i]) + y[k]*(x[i]-x[j]) + (x[j]*y[i] - x[i]*y[j])) > 0)
  45.     {
  46.         p = (x[i]+x[j])/2 - (y[j]-y[i])*sqrt(3.0)/2;
  47.         q = (y[i]+y[j])/2 - (x[i]-x[j])*sqrt(3.0)/2;
  48.     }
  49.     double a1 = q-y[k];
  50.     double b1 = x[k]-p;
  51.     double c1 = y[k]*p-x[k]*q;
  52.     p = (x[i]+x[k])/2 + (y[k]-y[i])*sqrt(3.0)/2;
  53.     q = (y[i]+y[k])/2 + (x[i]-x[k])*sqrt(3.0)/2;
  54.     if ((p*(y[k]-y[i]) + q*(x[i]-x[k]) + (x[k]*y[i] - x[i]*y[k])) * 
  55.         (x[j]*(y[k]-y[i]) + y[j]*(x[i]-x[k]) + (x[k]*y[i] - x[i]*y[k])) > 0)
  56.     {
  57.         p = (x[i]+x[k])/2 - (y[k]-y[i])*sqrt(3.0)/2;
  58.         q = (y[i]+y[k])/2 - (x[i]-x[k])*sqrt(3.0)/2;
  59.     }
  60.     double a2 = q-y[j];
  61.     double b2 = x[j]-p;
  62.     double c2 = y[j]*p-x[j]*q;
  63.     p = -(c1*b2-c2*b1)/(a1*b2-a2*b1);
  64.     q = -(a1*c2-a2*c1)/(a1*b2-a2*b1);
  65.  
  66.     if (j>=n)
  67.     {
  68.         x[j] = p;
  69.         y[j] = q;
  70.     }
  71.     else
  72.     {
  73.         x[m+n] = p;
  74.         y[m+n] = q;
  75.         ::p[k] = m+n;
  76.         if (::p[i] == j)
  77.         {
  78.             ::p[i] = m+n;
  79.             ::p[m+n] = j;
  80.         }
  81.         else
  82.         {
  83.             ::p[j] = m+n;
  84.             ::p[m+n] = i;
  85.         }
  86.         m++;
  87.     }
  88.     return true;
  89. }
  90.  
  91. int main()
  92. {
  93.     int t;
  94.     scanf("%d", &t);
  95.     while (t--)
  96.     {
  97.         int i, j, k;
  98.         scanf("%d", &n);
  99.         m = 0;
  100.         for (i=0; i<n; i++)
  101.             scanf("%lf%lf", x+i, y+i);
  102.  
  103.         memset(p, 0, sizeof(p));
  104.         memset(w, 0, sizeof(w));
  105.         w[0] = true;
  106.         for (i=0; i<n; i++)
  107.             r[i] = sqr(x[i]-x[0]) + sqr(y[i]-y[0]);
  108.  
  109.         for (k=1; k<n; k++)
  110.         {
  111.             int c;
  112.             for (c=0; w[c]; c++);
  113.             for (i=c+1; i<n; i++)
  114.                 if (!w[i] && r[i] < r[c])
  115.                     c = i;
  116.             w[c] = true;
  117.             for (i=0; i<n; i++)
  118.                 if (!w[i])
  119.                 {
  120.                     double d=sqr(x[i]-x[c]) + sqr(y[i]-y[c]);
  121.                     if (r[i] > d)
  122.                     {
  123.                         p[i] = c;
  124.                         r[i] = d;
  125.                     }
  126.                 }
  127.         }
  128.  
  129.         for (k=0; k<1; k++)
  130.         {
  131.             for (i=1; i<n+m; i++)
  132.                 for (j=i+1; j<n+m; j++)
  133.                     if (p[i] == p[j])
  134.                         optimize(i, p[i], j);
  135.  
  136.             for (i=1; i<n+m; i++)
  137.                 if (p[i] > 0)
  138.                     optimize(p[p[i]], p[i], i);
  139.         }
  140.  
  141.         printf("%d\n", m);
  142.         for (i=0; i<m; i++)
  143.             printf("%lf %lf\n", x[i+n], y[i+n]);
  144.         printf("%d\n", n+m-1);
  145.         double res = 0;
  146.         for (i=1; i<n+m; i++)
  147.         {
  148.             printf("%d %d\n", i, p[i]);
  149.             res += dist(i, p[i]);
  150.         }
  151. //        printf("%lf\n", res);
  152.     }
  153.     return 0;
  154. }
  155.