Oops...Solaris wrote:All the points stated in this problem will be on the X axes, so all Y co-ordinates should be zero. I dont know what did u mean by X-Y coordinates?
My algorithm was to get to the highest point possible from each current position. Hope this will help.
What I ment actually by X was the left coordinate (L), and Y was the right coordinate(R)... - set 'current' to 0, find the line segment with left coordinate <= current and right coordinate the rightmost possible; then i updated current with the right coordinate of that segment, and repeated this until left > currentMinilek wrote:
I'm getting SIGSEV but am not quite sure why (I tried putting assert's all over the place but still no SIGABRT).
Code: Select all
Program received signal SIGSEGV, Segmentation fault.
0x080485a1 in main () at minilek.c:32
32 best->l = best->r = -1;
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define MaxN 100000
void Swap (long *A, long *B) { long C = *A; *A = *B; *B = C; }
int main (void) {
long I, J, T, M, N, K, OK, Sol, L [MaxN], R [MaxN], X [MaxN], Y [MaxN];
scanf ("%d", &T);
for (; T > 0; T--) {
scanf ("%d", &M);
N = 0;
while (scanf ("%d%d", &L [N], &R [N]) != EOF) {
if (! L [N] && ! R [N]) break;
if (L [N] > R [N]) Swap (&L [N], &R [N]);
if (N > 0 && L [N-1] == L [N] && R [N-1] < R [N]) R [N-1] = R [N--];
for (I = N; L [N] < L [N-1] && I > 0; I--) Swap (&L [N-1], &L [N]), Swap (&R [N-1], &R [N]);
N++;
}
Sol = 0;
for (I = K = 0; I < N && K < M; I = J) {
OK = K;
for (J = I; L [J] <= OK && R [J] >= OK && J < N; J++)
if (R [J] > K) K = R [J];
if (OK != K) X [Sol] = L [J-1], Y [Sol] = R [J-1], Sol++;
else { Sol = 0; break; }
}
printf ("%d\n", Sol);
for (I = 0; I < Sol; I++) printf ("%d %d\n", X [I], Y [I]);
if (T > 1) printf ("\n");
}
} Code: Select all
//10020 Minimal coverage
#include <iostream>
#include <cstdlib>
using namespace std;
struct Segment
{
long l,r;
};
Segment segment[100000];
long choose[100000];
int compare(const void *a,const void *b)
{
Segment *p=(Segment*)a;
Segment *q=(Segment*)b;
if(p->l > q->l)
return 1;
else
if(p->l < q->l)
return -1;
else
if(p->r < q->r)
return -1;
else
if(p->r > q->r)
return 1;
else
return 0;
}
int main(int argc,char *argv[])
{
long M,n,s;
long i;
long l,r;
long curLeft;
long maxRight,pos;
long testCase;
cin>>testCase;
while(testCase-->=1)
{
cin>>M;
n=0;
cin>>l>>r;
while(l!=0 || r!=0)
{
if(!(l>M || r<0))
{
segment[n].l=l;
segment[n].r=r;
n++;
}
cin>>l>>r;
}
qsort(segment,n,sizeof(Segment),compare);
curLeft=0;
maxRight=-1;
pos=0;
s=0;
for(i=0;i<n;i++)
{
if(segment[i].l<=curLeft)
{
if(segment[i].r>maxRight)
{
pos=i;
maxRight=segment[i].r;
}
}
else
{
if(maxRight==-1)
{
break;
}
else
{
choose[s]=pos;
s++;
curLeft=segment[pos].r;
maxRight=-1;
}
}
}
choose[s]=pos;
s++;
curLeft=segment[pos].r;
maxRight=-1;
if(curLeft>=M)
{
cout<<s<<endl;
for(i=0;i<s;i++)
cout<<segment[choose[i]].l<<" "<<segment[choose[i]].r<<endl;
}
else
cout<<0<<endl;
cout<<endl;
}
}
Code: Select all
In the following lines, the coordinates of segments, sorted by their left end (Li), should be printed in the same format as in the input.Code: Select all
10
4
-1 3.1
0 1
0 2.1
2.1 3
3.100002 4
0 0
4
-1 3.1
0 1
0 2.1
2.1 3
3.1000002 4
0 0
4
-1.100101 3
0.557 1
1.1 2
2 3
2.99 4.141414141414141
0 0
1
-1.000 0.11
-5 -3.2
2 5.7
0 0
1
-1 0
-10.1000 0.25
0.2499999 1
0 0
5
0 3
0 4
4 5
0 0
4
-1 3.1
0 1
0 2.1
2.1 3
3.099999 4
0 0
4
0 1
1 20
1 19
0 0
5
0 1
3 5
-10 4.2
4.1 11
0 0
1
-1 -2
0 1
0 0
Code: Select all
0
2
-1 3.1
3.1000002 4
2
-1.100101 3
2.99 4.141414141414141
0
2
-10.1000 0.25
0.2499999 1
2
0 4
4 5
2
-1 3.1
3.099999 4
2
0 1
1 20
2
-10 4.2
4.1 11
1
0 1Code: Select all
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define SIZE 100001
#define EPS 1e-6
typedef struct {
double l,r;
char one[17];
char two[17];
}point;
point arr[SIZE];
int pos[SIZE];
void refresh()
{
long i;
for(i=0;i<SIZE;i++){arr[i].l=arr[i].r=pos[i]=0;}
}
int comp(const void *a,const void *b)
{
if (((point *)a)->l>((point *)b)->l) return 1;
if (((point *)a)->l<((point *)b)->l) return -1;
if (((point *)a)->l==((point *)b)->l)
{
if (((point *)a)->r<((point *)b)->r)return 1;
if (((point *)a)->r>((point *)b)->r) return -1;
}
return 0;
}
void main()
{
long N,i,num,j;
double a,b,M,cur_r,temp;
char p[17],q[17];
/*freopen("d:\\in10020t.txt","r",stdin);
freopen("d:\\out10020.txt","w",stdout);
clrscr();*/
scanf("%ld",&N);
while(N-->0)
{
scanf("%lf",&M);
i=0;
while(scanf("%s %s",p,q)==2)
{
sscanf(p,"%lf",&a);
sscanf(q,"%lf",&b);
if(a+b==0.0)break;
if(a<0.0 && b<=0.0)continue;
if(a>b)
{
temp=a;a=b;b=temp;
strcpy(arr[i].one,q);
strcpy(arr[i].two,p);
}
strcpy(arr[i].one,p);
strcpy(arr[i].two,q);
if(a<=M)
{
if(fabs(a)>=EPS)arr[i].l=a;
else {arr[i].l=0;}
arr[i].r=b;
i++;
}
}
qsort(arr,i,sizeof(point),comp);
cur_r=0;
num=0;
for(j=0;j<i;j++)
{
if((arr[j].l<=cur_r || arr[j].l-cur_r<=EPS) && arr[j].r>cur_r )
{
num++;
pos[j]=1;
cur_r=arr[j].r;
}
if(cur_r>=M)break;
}
if(cur_r>=M)
{
printf("%ld\n",num);
for(j=0;j<i && num;j++)
{
if(pos[j])
{
num--;
printf("%s %s\n",arr[j].one,arr[j].two);
}
}
}
else printf("0\n");
refresh();
if(N>0)printf("\n");
}
}
Code: Select all
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
struct line
{
double l, r;
char cl[20];
char cr[20];
};
int n;
double m;
line arre[MAX];
int sort(const void *a, const void *b)
{
struct line *aa = (line*)a;
struct line *bb = (line*)b;
if (aa->l != bb->l)
{
if (aa->l < bb->l)
return -1;
else
if (aa->l > bb->l)
return 1;
else
return 0;
}
else
{
if (bb->r < aa->r)
return -1;
else
if (bb->r > aa->r)
return 1;
else
return 0;
}
}
bool Igual(double a, double b)
{
return fabs(a - b) <= 0.000001;
}
bool Esta(double val, double ini, double fin)
{
return (ini < val || Igual(ini, val)) && (val < fin || Igual(val, fin));
}
int main()
{
int test, t, h, mark[MAX];
char c1[20], c2[20];
double ini, fin;
scanf("%d", &test);
while (test--)
{
scanf("%lf", &m);
scanf("%s %s", &c1, &c2);
sscanf(c1, "%lf", &ini);
sscanf(c2, "%lf", &fin);
n = 0;
while (ini || fin)
{
if (Esta(0, ini, fin) || Esta(m, ini, fin))
{
arre[n].l = ini;
arre[n].r = fin;
strcpy(arre[n].cl, c1);
strcpy(arre[n].cr, c2);
++n;
}
scanf("%s %s", &c1, &c2);
sscanf(c1, "%lf", &ini);
sscanf(c2, "%lf", &fin);
}
if (n)
{
qsort(arre, n, sizeof(line), sort);
mark[t = 1] = 0;
for (int i = 1; i < n; i++)
{
if (t == 1)
{
if (Esta(arre[i].l, arre[mark[1]].l, arre[mark[1]].r) && arre[i].r > arre[mark[0]].r)
mark[++t] = i;
}
else
{
if (Esta(arre[i].l, arre[mark[t - 1]].l, arre[mark[t - 1]].r) && arre[i].r > arre[mark[t]].r)
mark[t] = i;
}
if (arre[mark[t]].l == 0)
{
h = mark[t];
mark[t = 1] = h;
}
if (arre[mark[t]].r > m && Igual(arre[mark[t]].r, m))
break;
}
}
else
puts("0");
if (arre[mark[t]].r > m || Igual(arre[mark[t]].r, m))
{
printf("%d\n", t);
for (int i = 1; i <= t; i++)
printf("%s %s\n", arre[mark[i]].cl, arre[mark[i]].cr);
}
else
puts("0");
if (test > 0)
putchar('\n');
}
return 0;
}