Tävlingsprogrammering/Uppgifter/Pyramidspaning

Lösning

Varje pyramid ligger antingen utom synhåll från vägen (om s<|x|), som för P₂ i figuren nedan, eller inom synhåll i ett intervall, som för P₁. I det första fallet ska pyramiden inte behandlas alls. I det senare fallet kan intervallets start-och slutpunkter lätt bestämmas genom att beräkna avståndet d i figuren nedan med Pytagoras sats.

Fil:Tävlingsprogrammering-pyramidspaning3.png

Problemet har därmed reducerats till att bland en mängd intervall hitta den största delmängd som överlappar på åtminstone någon sträcka. Ett enkelt sätt att lösa detta problem är att först sortera listan (yy i exemplet nedan) med start- och slutpunkter och sedan "scanna" från det lägsta till det högsta yy-värdet och hela tiden hålla reda på hur många intervall man är inne i. En startpunkt ökar detta antal med 1 och en slutpunkt minskar antalet med 1. Sedan är det bara att spara det maximala antalet samt vilket intervall detta förekommer i (det räcker med startpunkten: den efterkommande punkten i yy-listan måste ju vara en slutpunkt för annars skulle man se ännu fler pyramider efter denna punkt). Att man ska hitta det längsta intervallet är bara en teknisk detalj, man måste förutom det maximala antalet också spara längden på det hittills längsta intervallet med det maximala antalet synliga pyramider.

Lösningsexempel i C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double yy[20000];
int t[20000],ord[20000];

int fcmp(const void *p1, const void *p2) { Mall:Komm
  int i1=*(int*)p1,i2=*(int*)p2;
  return (yy[i1]>yy[i2])?1:-1;
}

int main(){
  int N,n,max,now,bra,i,nsol;
  double x,y,h,r,d,length;
  scanf("%d",&N);
  n=0;
  for(i=0;i<N;i++) {
    scanf("%lf %lf %lf", &x,&y,&h);
    r=3.57*sqrt(h)+4.65;
    if(fabs(x)<r) {            Mall:Komm
      d=sqrt(r*r-x*x);
      yy[n]=y-d;    Mall:Komm
      t[n++]=1;   
      yy[n]=y+d;   Mall:Komm
      t[n++]=-1;
    }
  }
  for(i=0;i<n;i++) ord[i]=i;   Mall:Komm
  qsort(ord,n,sizeof(int),fcmp);          Mall:Komm
  max=0;        Mall:Komm
  now=0;        Mall:Komm
  for(i=0;i<n;i++) {               Mall:Komm
    now+=t[ord[i]];        Mall:Komm
    if(now>max) || ((now==max) && (yy[ord[i+1]]-yy[ord[i]]>length))) {   Mall:Komm
      max=now;                                                              Mall:Komm
      length=yy[ord[i+1]]-yy[ord[i]];
      bra=i;                                                               Mall:Komm
      }
    } 
  }
  printf("%d\n%.4lf %.4lf\n",max, yy[ord[bra]],yy[ord[bra+1]]);  Mall:Komm
  return 0;
}