ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

## Обсуждение задачи 1151. Радиомаяки

Who can explain me the problem,I think maybe I misunderstand it.
Послано ABCDEFG 26 окт 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 (-)
Послано Michael Rybak (accepted@ukr.net) 26 окт 2004 19:35
Re: I believe you understand the problem correctly. You must have a mistake in your code (-)
Послано ABCDEFG 27 окт 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;
}

{
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){
--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 (-)
Послано ABCDEFG 28 окт 2004 08:29
who can help me?
Re: Who can explain me the problem,I think maybe I misunderstand it.
Послано ABCDEFG 31 окт 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.
Послано bug27 12 апр 2005 19:33
I'm sure your understanding is right.