Назад к лучшим решениям Status: AC, problem ZELC, contest ZEL07. By levlam (Levin Aleksey), 2007-03-14 01:14:20.
  1. #include <stdio.h>
  2. #include <math.h>
  3. double x[6005], y[6005], z[6005], r[3], a[8000], ax[8000], ay[8000];
  4. double sqrt3_2=0.86602540378443864676372317075294, sqrt3;
  5. int p[3005], pr[3005], n, t, b[25005], e[25005], kk, f[25005], m, next[25005], prev[25005], c[8000], g, mn;
  6. int X[6005], Y[6005], d[3005], XX, YY;
  7.  
  8. void qsort(int l, int r)
  9. {
  10.    int i=l, j=r, tt;
  11.    double x=a[(l+r)>>1], t;
  12.    while (i<=j)
  13.    {
  14.       while (a[i]>x) i++;
  15.       while (a[j]<x) j--;
  16.       if (i<=j)
  17.       {
  18.          t=a[i], a[i]=a[j], a[j]=t;
  19.          t=ax[i], ax[i]=ax[j], ax[j]=t;
  20.          t=ay[i], ay[i]=ay[j], ay[j]=t;
  21.          tt=c[i], c[i++]=c[j], c[j--]=tt;         
  22.       }
  23.    }
  24.    if (l<j) qsort(l,j);
  25.    if (i<r) qsort(i,r);
  26. }
  27.  
  28. double D(int i, int j)
  29. {
  30.    double dx=x[i]-x[j], dy=y[i]-y[j];
  31.    return dx*dx+dy*dy;
  32. }
  33.  
  34. int DD(int i, int j)
  35. {
  36.    int dx=X[i]-X[j], dy=Y[i]-Y[j];
  37.    return dx*dx+dy*dy;
  38. }
  39.  
  40. int DDD(int j)
  41. {
  42.    int dx=XX-X[j], dy=YY-Y[j];
  43.    return dx*dx+dy*dy;
  44. }
  45.  
  46. void rot(int i, int j, int k)
  47. {
  48.    x[k]=x[i]+(x[j]-x[i])*0.5-(y[j]-y[i])*sqrt3;
  49.    y[k]=y[i]+(y[j]-y[i])*0.5+(x[j]-x[i])*sqrt3;
  50. }
  51.  
  52. void add(int x, int y)
  53. {
  54.    b[kk]=x;
  55.    e[kk]=y;
  56.    next[kk]=f[x];
  57.    prev[f[x]]=kk;
  58.    prev[kk]=-1;
  59.    f[x]=kk++;
  60. }
  61.  
  62. void addd(int x, int y)
  63. {
  64.    add(x,y);
  65.    add(y,x);
  66. }
  67.  
  68. void del(int k)
  69. {
  70.    if (prev[k]==-1) f[b[k]]=next[k];
  71.    else next[prev[k]]=next[k];
  72.    if (next[k]!=-1) prev[next[k]]=prev[k];
  73.    next[k]=f[b[k]];   
  74.    b[k]=e[k]=-1;
  75. }
  76.  
  77. void dell(int k)
  78. {
  79.    del((k>>1)<<1);
  80.    del(((k>>1)<<1)+1);   
  81. }
  82.  
  83. int can(int j, int k)
  84. {
  85.    int x1, y1, x2, y2;
  86.    double tt;
  87.    if (e[k]==b[j]) return 0;
  88.    x1=X[b[j]]-X[e[j]];
  89.    y1=Y[b[j]]-Y[e[j]];
  90.    x2=X[e[k]]-X[b[k]];
  91.    y2=Y[e[k]]-Y[b[k]];
  92.    tt=x1*x2+y1*y2;
  93.    if (tt>=0.0 || tt*tt<0.1*DD(b[j],e[j])*DD(b[k],e[k]))
  94.    {
  95.       if (x1*y2<x2*y1) return 1;
  96.       else return -1;
  97.    }
  98.    else return 0;
  99. }
  100.  
  101. void getpoint(int j, int k, int s)
  102. {
  103.    double x1, y1, z1, x2, y2, z2;
  104.    int ii, jj;
  105.    sqrt3=s*sqrt3_2;
  106.    rot(b[j],e[k],n+m+1);
  107.    rot(e[k],e[j],n+m+2);
  108.  
  109.    ii=e[j], jj=n+m+1;
  110.    x1=y[ii]-y[jj];
  111.    y1=x[jj]-x[ii];
  112.    z1=x[ii]*y[jj]-x[jj]*y[ii];
  113.  
  114.    ii=b[j], jj=n+m+2;
  115.    x2=y[ii]-y[jj];
  116.    y2=x[jj]-x[ii];
  117.    z2=x[ii]*y[jj]-x[jj]*y[ii];
  118.  
  119.    x[mn]=y1*z2-y2*z1;
  120.    y[mn]=x2*z1-x1*z2;
  121.    z1=x1*y2-x2*y1;
  122.    x[mn]/=z1;
  123.    y[mn]/=z1;
  124. }
  125.  
  126. void addpoint(int j, int k, int i)
  127. {
  128. //   a[g]=D(b[j],e[j])+D(b[k],e[k])-D(b[j],i)-D(b[k],i)-D(e[k],i);
  129.    a[g]=sqrt(D(b[j],e[j]))+sqrt(D(b[k],e[k]))-sqrt(D(b[j],i))-sqrt(D(b[k],i))-sqrt(D(e[k],i));
  130.    ax[g]=x[i];
  131.    ay[g]=y[i];
  132.    c[g++]=k+(j<<13);
  133. }
  134.  
  135. void out(void)
  136. {
  137.    int i, t;
  138.    printf("%d\n", m);
  139.    for (i=0; i<m; i++) printf("%.15lf %.15lf\n", x[n+i], y[n+i]);
  140.    printf("%d\n", m+n-1);
  141.    for (i=0; i<m+n; i++)
  142.       for (t=f[i]; t!=-1; t=next[t])
  143.          if (b[t]<e[t]) printf("%d %d\n", b[t], e[t]);
  144. }
  145.  
  146. int main(void)
  147. {
  148.    int i, j, k, tn, nt, min, s, tt, dmin;
  149.    int *dd;
  150. //   freopen("input.txt", "r", stdin);
  151. //   freopen("output.txt", "w", stdout);
  152.    scanf("%d", &nt);
  153.    for (tn=0; tn<nt; tn++)
  154.    {
  155.       scanf("%d", &n);
  156.       m=kk=0, mn=n;      
  157.       for (i=0; i<n; i++)
  158.          scanf("%lf%lf", &x[i], &y[i]), f[i]=-1, X[i]=x[i]+0.5, Y[i]=y[i]+0.5;
  159.       for (i=1; i<n; i++)
  160.          d[i-1]=1000000000, p[i-1]=i;
  161.       t=n-1;
  162.       j=0;
  163.       while (t>0)
  164.       {
  165.          XX=X[j], YY=Y[j];
  166.          for (min=i=0, dd=d, dmin=*dd; i<t; i++, dd++)
  167.          {
  168.             if ((tt=DDD(p[i]))<*dd) *dd=tt, pr[i]=j;
  169.             if (*dd<dmin) min=i, dmin=*dd;
  170.          }
  171.          addd(pr[min], p[min]);
  172.          j=p[min];
  173.          t--;
  174.          p[min]=p[t];
  175.          d[min]=d[t];
  176.          pr[min]=pr[t];
  177.       }
  178.       for (g=i=0; i<n; i++)
  179.          for (j=f[i]; j!=-1; j=next[j])
  180.             for (k=f[e[j]]; k!=-1; k=next[k])
  181.                if (j<k && (s=can(j,k)))
  182.                {
  183.                   getpoint(j, k, s);
  184.                   addpoint(j, k, n);
  185.                }
  186.       qsort(0, g-1);
  187.       for (i=0; i<g && m<n; i++)
  188.       {
  189.          j=c[i];
  190.          k=j&8191;
  191.          j>>=13;
  192.          if (b[j]>=0 && b[k]>=0)
  193.          {
  194. //            getpoint(j, k, can(j,k));
  195.             x[mn]=ax[i];
  196.             y[mn]=ay[i];
  197.             f[mn]=-1;
  198.             addd(b[j],mn);
  199.             addd(b[k],mn);
  200.             addd(e[k],mn);
  201.             dell(j);
  202.             dell(k);
  203.             m++;
  204.             mn++;
  205.          }
  206.       }
  207. /*      for (i=0; i<m+n && m<n; i++)
  208.          for (j=f[i]; j!=-1 && m<n; j=next[j])
  209.          {
  210.             for (k=f[e[j]]; k!=-1; k=next[k])
  211.                if (s=can(j,k)) break;
  212.             if (k!=-1)
  213.             {
  214.                getpoint(j, k, s);
  215.                f[m+n]=-1;
  216.                addd(i,mn);
  217.                addd(b[k],mn);
  218.                addd(e[k],mn);
  219.                dell(j);
  220.                dell(k);
  221.                m++;
  222.                mn++;
  223.             }
  224.          }*/
  225.       out();
  226.    }
  227.    return 0;
  228. }