Tävlingsprogrammering/Uppgifter/Pyramidspaning

Pyramidspaning (PO-onlinekvalet 2008)

Vi antar nu att du vunnit Programmeringsolympiaden och befinner dig i Egypten, omgiven av pyramider av varierande höjd. Vi antar också att marken är alldeles plan så att du har fri sikt oändligt långt åt alla håll. På grund av jordklotets krökning finns det ändå ett gränsavstånd s kilometer, för hur långt bort du kan se en given pyramid, därefter kommer den "nedanför horisonten". Avståndet s beror naturligtvis på pyramidens höjd: ju högre den är desto längre bort kan den ses, eftersom vi räknar att vi ser pyramiden även om bara den yttersta spetsen sticker upp ovanför horisonten.

Om vi antar att dina ögon befinner sig 1.7 meter över marken så kan s beräknas med formeln

$s=4.65+3.57{\sqrt {h}}$

där h är pyramidens höjd i meter, medan s är det maximala siktavståndet i kilometer.

Du färdas på en väg som genomkorsar öknen och som vi antar är oändligt lång, helt rak och följer y-axeln (x=0) i ett tänkt koordinatsystem. Skriv ett program som, givet koordinaterna samt höjden för ett antal pyramider, beräknar hur många pyramider du maximalt kan se samtidigt från någon plats utmed vägen samt anger det längsta intervall där detta maximala antal kan observeras. Programmet behöver inte ta hänsyn till att pyramiderna kan skymma varandra.

Indata

På första raden står ett heltal: antalet pyramider (1 ≤ n ≤ 10000). Därefter följer n rader med tre decimaltal x, y och h på varje rad, vilka anger koordinaterna (−1000 ≤ x,y ≤ 1000) i kilometer samt höjden (1 ≤ h ≤ 1000) i meter för varje pyramid.

Utdata

På första raden ska programmet skriva ut ett heltal: det maximala antalet pyramider som kan ses samtidigt från någon plats utmed vägen. På andra raden ska programmet skriva ut två decimaltal y_min och y_max, vilka specificerar det längsta kontinuerliga intervall av vägen inom vilket det maximala antalet pyramider kan ses. Talen y_min och y_max måste vara korrekta med minst tre decimalers noggrannhet.

Exempel: Indata

4
-11.0 -17.5 40.5
-20.5 15.8 35.0
42.5 12.7 116.4
-15.3 46.85 8.05

Exempel: Utdata

3
5.1448 7.5615

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.

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) { //Jämförelsefunktion till qsort
  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) {            //Om pyramiden är synlig i ett intervall av linjen
      d=sqrt(r*r-x*x);
      yy[n]=y-d;    //Lägg in intervallets startpunkt (t=+1) i listan yy
      t[n++]=1;   
      yy[n]=y+d;   //Lägg in intervallets slutpunkt (t=-1) i listan yy
      t[n++]=-1;
    }
  }
  for(i=0;i<n;i++) ord[i]=i;   //"Pekare" till index i yy- och t-tabellerna
  qsort(ord,n,sizeof(int),fcmp);          //Sortera pekar-arrayen efter stigande yy-värden
  max=0;        //Högsta antalet överlappande intervall hittills
  now=0;        //Det aktuella antalet överlappande intervall
  for(i=0;i<n;i++) {               //Scanna från låga till höga yy-värden
    now+=t[ord[i]];        //Öka eller minska now beroende på om vi går in i eller ut ur ett intervall
    if(now>max) || ((now==max) && (yy[ord[i+1]]-yy[ord[i]]>length))) {   //Om högre antal än max eller längre intervall uppnås...
      max=now;                                                              //... så uppdatera de optimala värdena...
      length=yy[ord[i+1]]-yy[ord[i]];
      bra=i;                                                               // ... och spara indexet till intervallets startpunkt
      }
    } 
  }
  printf("%d\n%.4lf %.4lf\n",max, yy[ord[bra]],yy[ord[bra+1]]);  //Skriv ut det "bra" intervallets startpunkt samt den efterföljande punkten i yy-listan
  return 0;
}