```
#include<stdio.h>
#include<iostream.h>
#include<math.h>
#include<conio.h>
#include<graphics.h>
#include<dos.h>
#include<process.h>
#include<time.h>
#include "stst.h"
int main(void)
{
int n,n1=0,n2=0;// no of Demand points
int *x_list,*y_list;
int x_no,y_no,st_can_no,visited_no,rx1_no,rx2_no,ry1_no,ry2_no;
float y_mid,x_mid,mid;
int xmin,xmax;
int i,j,k,insertpos,insertpos1;
int x,y;
int wrst_no;
long int mincost,cost1,cost2;
vertex *temp,*temp1, *uterm,*lterm;
/*vertex *state;
vertex * st_can,temp;
vertex centre1,centre2;
int found =0;
edge *wrst; */
edge tedge;
long int wrstcost;
// int gd = DETECT,gm;
// int maxx=1,maxy=1;
int long x_range,y_range,rx_range,ry_range;
float scale,scale1;
int long p1,q1,p2,q2;
int x1,y1,x2,y2,x3,y3;
long int r,total_weight, reg_n;
time_t stime,ftime;
clrscr();
cout<<"--------------------------------------------------"<<endl;
cout <<" Input "<<endl;
cout<<"--------------------------------------------------"<<endl;
cout<<"\nEnter the no of Points: - ";
cin>>n;
temp=new vertex[n];
temp1=new vertex[n];
uterm=new vertex[n];
lterm=new vertex[n];
x_list=new int[n];
y_list=new int[n];
// st_can=new vertex[n*(n-1)];
cout<<"\nEnter the co-ordinates of node 1 :";
cin>>x;
cin>>y;
x_list[0]=x;
x_no=1;
y_list[0]=y;
y_no=1;
temp[0].xpos=x;
temp[0].ypos=y;
for(i=1;i<n;i++)
{
cout<<"\nEnter the co-ordinate of Node:" << i+1 <<" : " ;
cin>>x;
cin>>y;
/********** Insert X Value into sorted X_list***************/
j=0;
while((x_list[j]<=x)&&(j<x_no))
j++;
insertpos=j;
x_no++;
for(j=x_no-1;j>insertpos;j--)
x_list[j]=x_list[j-1];
x_list[insertpos]=x;
/********** Insert Y Value into sorted X_list***************/
j=0;
while((y_list[j]<=y)&&(j<y_no))
j++;
insertpos=j;
y_no++;
for(j=y_no-1;j>insertpos;j--)
y_list[j]=y_list[j-1];
y_list[insertpos]=y;
j=0;
while((temp[j].xpos<=x)&&(j<i))
j++;
insertpos=j;
for(j=i;j>insertpos;j--)
{
temp[j].xpos=temp[j-1].xpos;
temp[j].ypos=temp[j-1].ypos;
}
temp[insertpos].xpos=x;
temp[insertpos].ypos=y;
}
xmin=x_list[0];
xmax=x_list[n-1];
cout<<"Xmin= "<<xmin;
cout<<"\nXmax= "<<xmax;
cout<<"\nValues Of X list "<<endl ;
/*****display x list********/
{
for(i=0;i<x_no;i++)
cout<<x_list[i]<<endl;
}
cout<<"\nValues Of Y list "<<endl ;
/*****display x list********/
{
for(i=0;i<y_no;i++)
cout<<y_list[i]<<endl;
}
/*******Dispaly Of Temp list **********/
cout<<"display of Temp"<<endl;
for (i=0;i<n; i++)
{
cout<<temp[i].xpos<<" , "<<temp[i].ypos<<" ,"<<endl;
}
if(y_no%2!=0)
{
y_mid=y_list[(y_no+1)/2 - 1];
cout<<"Y-Median:= "<<y_mid;
}
else
{
mid = y_list[y_no/2] + y_list[(y_no/2)-1];
y_mid=mid/2;
cout<<"Y-Median:= "<<y_mid;
}
tedge.start.xpos=xmin;
tedge.start.ypos=y_mid;
tedge.end.xpos=xmax;
tedge.end.ypos=y_mid;
cout<<"\n"<<tedge.start.xpos<<","<<tedge.start.ypos <<"->"<<tedge.end.xpos<<","<<tedge.end.ypos;
j=0;
k=0;
for(i=0;i<n;i++)
{
if(temp[i].ypos>y_mid)
{
uterm[j].xpos= temp[i].xpos;
uterm[j].ypos=temp[i].ypos;
n1++;
j++;
}
else
{
if(temp[i].ypos!=y_mid)
{
lterm[k].xpos= temp[i].xpos;
lterm[k].ypos=temp[i].ypos;
n2++;
k++;
}
}
/* for(j=0;j<n1;j++)
{
if(uterm[j].xpos<uterm[j+1].xpos)
{
temp1[j].xpos=uterm[j].xpos;
uterm[j].xpos=uterm[j+1].xpos;
uterm[j+1].xpos= temp1[j].xpos;
}
} */
}
cout<<"\ndisplay of UTerm"<<endl;
//cout<<"\n"<<n1<<"\n";
for (j=0;j<n1; j++)
{
cout<<uterm[j].xpos<<" , "<<uterm[j].ypos<<endl;
}
cout<<"\ndisplay of LTerm"<<endl;
//cout<<"\n"<<n1<<"\n";
for (k=0;k<n2; k++)
{
cout<<lterm[k].xpos<<" , "<<lterm[k].ypos<<endl;
}
getch();
return 0;
}
```