A point (x1,y1) \'dominates\' (x2,y2) in the plane if both x1>=x2 and y1>=y2 hol

Question

A point (x1,y1) 'dominates' (x2,y2) in the plane if both x1>=x2 and y1>=y2 hold. (i.e. (5,2) dominates (2,1)). A point p is a maximal point of a set S if there doesn't exist another point in S that dominates p. The problem at hand is to report all maximal points of a given set. To do this, sort all the x-coordinate points in ascending order. Then check the points one by one, right to left, recording the largest y-coordinate seen thus far. For each point, if its y-coordinate is larger than the largest y-coordinate of all the points to its right, report it as a maximal point. (Note: the rightmost point is always a maximal point). We can assume that x-coordinates are distinct. For example, the following 10 x-coords and y-coords are given as such (x y): 12 5 29 7 0 13 55 9 47 2 23 -5 -7 90 11 33 25 -24 21 7 the program should then ?nd the maximal points among these 10 points, and report the maximal points in decreasing order of x-coordinates. To report a point, print its x-coordinate and y-coordinate in a single line (not allowed to use any sorting C library functions). from above, we expect the output 55 9 11 33 -7 90

Explanation / Answer

Please rate...

program:

====================================================

#include<stdio.h>
void main()
{
    int arx[10];
    int ary[10];
    int i,j,t,max;
    printf("Enter the 10 points: ");
    for(i=0;i<10;i++)
    {
        scanf("%d",&arx[i]);
        scanf("%d",&ary[i]);
    }


    for(i=0;i<10;i++)
    {
        for(j=0;j<9;j++)
        {
            if(arx[j]>arx[j+1])
            {
                t=arx[j];
                arx[j]=arx[j+1];
                arx[j+1]=t;

                t=ary[j];
                ary[j]=ary[j+1];
                ary[j+1]=t;
            }
        }
    }

    printf("The maximal points are: ");
    for(i=9;i>=0;i--)
    {
        max=ary[i];
        for(j=i;j<=9;j++)
        {
            if(max<=ary[j])max=ary[j];
        }
        if(ary[i]>=max)printf("%d %d ",arx[i],ary[i]);
    }
}

================================================

Sample output:

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.