ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1151. Radiobeacons

Who can explain me the problem,I think maybe I misunderstand it.
Posted by ABCDEFG 26 Oct 2004 19:09
While reading the information of the checkpoints,I can use there coordinates and the distance between it and a certain beacon to determin the range of the beacon.And as more information was read,the range will become smaller and smaller.So after the procedure,if I am sure the beacon is at a point,I output it and it's coordinates,otherwise I output UNKNOWN.Of course after sorting.

I think my algorithm is right if I did understand the idea.
But I got wa even on test 2,who can help me and tell me the meaning of the problem or give me your algorithm,thank you.
I believe you understand the problem correctly. You must have a mistake in your code (-)
Posted by Michael Rybak (accepted@ukr.net) 26 Oct 2004 19:35
Re: I believe you understand the problem correctly. You must have a mistake in your code (-)
Posted by ABCDEFG 27 Oct 2004 18:31
This is my code ,I don't think it's wrong ,could you help me checking it?

#include<iostream>
#include<string>
#include<memory>
#include<cstdio>
#include<cstring>
using namespace std;

//#define DEBUG

#ifndef DEBUG
FILE *fin=stdin;
#else
FILE *fin=fopen("1151.txt","r");
#endif


const long maxm=20;
const long maxn=11;
const long maxint=200;
//long map[maxn];
struct node{
    long map,minx,miny,maxx,maxy;
}list[maxn];
long n=0,m;

long insert(long x)
{
    long i;
    for(i=0;i<n;++i){
        if(list[i].map==x)return i;
    }
    list[n].map=x;
    list[n].minx=list[n].miny=1;
    list[n].maxx=list[n].maxy=200;
    ++n;
    return n-1;
}

void read()
{
    long x,y,a,b;
    char ch;
    fscanf(fin,"%ld,%ld",&x,&y);
    //cin>>x>>ch>>y;
    //cin.get(ch);
    ch=getc(fin);
    long i;
    while(ch!='\n'){
        fscanf(fin,"%ld-%ld",&a,&b);
        //cin>>a>>ch>>b;
        i=insert(a);
        if(x+b<list[i].maxx)list[i].maxx=x+b;
        if(x-b>list[i].minx)list[i].minx=x-b;
        if(y+b<list[i].maxy)list[i].maxy=y+b;
        if(y-b>list[i].miny)list[i].miny=y-b;
        if(fscanf(fin,"%c",&ch)==-1)break;
        //cin.get(ch);
        //if(cin.fail())break;
    }
}


int par(int p,int r)
{
    node temp=list[p];
    while(p<r){
        while(p<r&&list[r].map>=temp.map)--r;
        list[p]=list[r];
        while(p<r&&list[p].map<=temp.map)++p;
        list[r]=list[p];
    }
    list[p]=temp;
    return p;
}

void qsort(int p,int r)
{
    if(p<r){
        int q=par(p,r);
        qsort(p,q-1);
        qsort(q+1,r);
    }
}

int main(void)
{
    fscanf(fin,"%ld",&m);
    while(m>0){
        read();
        --m;
    }
    qsort(0,n-1);
    for(long i=0;i<n;++i){
        if(list[i].minx==list[i].maxx&&list[i].miny==list[i].maxy){
            //printf("%ld:%ld,%ld\n",list[i].map,list[i].maxx,list[i].maxy);
            cout<<list[i].map<<':'<<list[i].maxx<<','<<list[i].maxy<<endl;
        }
        else{
            //printf("%ld:UNKNOWN\n",list[i].map);
            cout<<list[i].map<<":UNKNOWN"<<endl;
        }
    }
    return 0;
}
Re: I believe you understand the problem correctly. You must have a mistake in your code (-)
Posted by ABCDEFG 28 Oct 2004 08:29
who can help me?
Re: Who can explain me the problem,I think maybe I misunderstand it.
Posted by ABCDEFG 31 Oct 2004 19:20
I rewrite my program and it still got wa on test 2,could anybody help me?????
Re: Who can explain me the problem,I think maybe I misunderstand it.
Posted by bug27 12 Apr 2005 19:33
I'm sure your understanding is right.