Отримання знань

дистанційна підтримка освіти школярів


Обнаружение края
http://acm.pku.edu.cn/JudgeOnline/problem?id=1009

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include < iostream >
#include < vector >
#include < set >
#include < algorithm >

using namespace std;

int w,h,total;
vector<pair<int,int> > v,ans;
set<int> note;

int calc_color(int x){
if(x<0 || x >= total) return -1;
for(int i=0;i<v.size();i++){
if(x < v[i].second) return v[i].first;
x -= v[i].second;
}
return -1;
}

#define abs(x) ((x)<0?(-(x)):(x))

void calc(){
ans.clear();
ans.push_back(make_pair(0,0));
int bef_pos = -1;
for(set<int>::iterator p = note.begin();p!=note.end();p++){
int t = *p;
int cur_color = calc_color(t);
int around[8];
int cur_diff = 0;
for(int i=0;i<8;i++) around[i] = -1;
if(t % w != 0){
around[0] = calc_color(t-w-1);
around[1] = calc_color(t -1);
around[2] = calc_color(t+w-1);
}
around[3] = calc_color(t-w );
around[4] = calc_color(t+w );
if(t % w != w-1){
around[5] = calc_color(t-w+1);
around[6] = calc_color(t +1);
around[7] = calc_color(t+w+1);
}
for(int i=0;i<8;i++){
if(around[i]==-1) continue;
cur_diff = max(cur_diff,abs(around[i]-cur_color));
}
if(ans[ans.size()-1].first == cur_diff){
ans[ans.size()-1].second += (t-bef_pos);
}else{
ans.push_back(make_pair(cur_diff,t-bef_pos));
}
bef_pos = t;
}
}

int main(void){
while(true){
cin >> w;
cout << w << endl;
if(w==0) break;
v.clear();
total = 0;
while(true){
int a,b;
cin >> a >> b;
if(a==0 && b == 0) break;
v.push_back(make_pair(a,b));
total += b;
}
h = total/w;
int cur_pos = 0;
note.clear();
for(int i=0;i<v.size();i++){
for(int j=-w;j<=w;j+=w)
for(int k=-2;k<=1;k++)
note.insert(cur_pos + j + k);
cur_pos += v[i].second;
}
note.insert(total-w);
note.insert(total-w-1);
note.insert(total -1);
set<int>::iterator sp = note.begin();
while(*sp < 0){
note.erase(sp);
sp = note.begin();
}
sp = note.end();sp--;
while(*sp >= total){
note.erase(sp);
sp = note.end();sp--;
}
calc();

for(int i=0;i<ans.size();i++)
if(ans[i].second != 0)
cout << ans[i].first << " "<<ans[i].second << endl;
cout << "0 0"<<endl;
}

return 0;
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)