USACO Window Area解題レポート
6608 ワード
やはり何度も間違えた.最初のアイデアは32768*32768の2次元マトリクスを構築し、遮蔽できるwindowに出会ったら遮蔽された部分をfalseにすることです.最後に隠されていない総数を見てみましょう.その後、この空間の利用が大きすぎて、百万級をはるかに超えていることが分かった.あとは、さえぎられると、それまでの小さなwindowが4つの小さなwindowになるというやり方です.flagマークアップの面ではずっと注意していなかったので、何度も間違えて提出に成功しました.
/*
ID: thestor1
LANG: C++
TASK: window
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cassert>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>
using namespace std;
const int SCREENSIZE = 32767;
class Window
{
public:
int x, y, X, Y;
int layer;
bool empty;
Window()
{
this->empty = true;
}
Window(int x, int y, int X, int Y)
{
this->x = x;
this->y = y;
this->X = X;
this->Y = Y;
this->layer = 0;
this->empty = false;
}
};
int ItoIndex(char I)
{
if ('a' <= I && I <= 'z')
{
return I - 'a';
}
if ('A' <= I && I <= 'Z')
{
return 26 + I - 'A';
}
assert('0' <= I && I <= '9');
return 52 + I - '0';
}
int main()
{
ifstream fin("window.in");
ofstream fout("window.out");
string line;
vector<Window> windows(62);
int top = 0, bottom = -1;
// std::vector<std::vector<bool> > screen(SCREENSIZE + 1, std::vector<bool>(SCREENSIZE + 1, false));
while (fin>>line)
{
// cout<<"line:["<<line<<"]"<<endl;
char type = line[0];
if (type == 'w')
{
// Create window: w(I,x,y,X,Y)
//w(a,10,132,20,12)
char I = line[2];
int x = 0, i = 4;
while (line[i] != ',')
{
x = x * 10 + line[i] - '0';
i++;
}
int y = 0;
i++;
while (line[i] != ',')
{
y = y * 10 + line[i] - '0';
i++;
}
int X = 0;
i++;
while (line[i] != ',')
{
X = X * 10 + line[i] - '0';
i++;
}
int Y = 0;
i++;
while (i != line.size() - 1)
{
Y = Y * 10 + line[i] - '0';
i++;
}
// cout<<"w("<<I<<","<<x<<","<<y<<","<<X<<","<<Y<<")"<<endl;
int minx = min(x, X), miny = min(y, Y), maxx = max(x, X), maxy = max(y, Y);
x = minx, y = miny, X = maxx, Y = maxy;
assert(x >= 1 && x <= X);
assert(y >= 1 && y <= Y);
assert(X > x && X <= SCREENSIZE);
assert(Y > y && Y <= SCREENSIZE);
// TODO Create
int index = ItoIndex(I);
if (!windows[index].empty)
{
continue;
}
windows[index].x = x;
windows[index].y = y;
windows[index].X = X;
windows[index].Y = Y;
windows[index].layer = top;
top++;
windows[index].empty = false;
}
else if (type == 't')
{
// Bring window to top: t(I)
char I = line[2];
// cout<<"t("<<I<<")"<<endl;
// TODO
int index = ItoIndex(I);
if (windows[index].layer != top - 1)
{
windows[index].layer = top;
top++;
}
}
else if (type == 'b')
{
// Put window on bottom: b(I)
char I = line[2];
// cout<<"b("<<I<<")"<<endl;
int index = ItoIndex(I);
if (windows[index].layer != bottom + 1)
{
windows[index].layer = bottom;
bottom--;
}
}
else if (type == 'd')
{
// Destroy window: d(I)
char I = line[2];
// cout<<"d("<<I<<")"<<endl;
int index = ItoIndex(I);
windows[index].empty = true;
}
else
{
assert(type == 's');
// Output percentage visible: s(I)
char I = line[2];
// cout<<"s("<<I<<")"<<endl;
int index = ItoIndex(I);
// for (int x = 1; x <= SCREENSIZE; ++x)
// {
// for (int y = 1; y <= SCREENSIZE; ++y)
// {
// screen[x][y] = false;
// }
// }
std::vector<Window> splits;
splits.push_back(windows[index]);
for (int i = 0; i < windows.size(); ++i)
{
if (i == index || windows[i].empty || windows[i].layer <= windows[index].layer)
{
continue;
}
assert(windows[i].layer > windows[index].layer);
std::vector<Window> newsplits;
for (int j = 0; j < splits.size(); ++j)
{
if (splits[j].empty)
{
continue;
}
int ox = max(windows[i].x, splits[j].x), oX = min(windows[i].X, splits[j].X);
int oy = max(windows[i].y, splits[j].y), oY = min(windows[i].Y, splits[j].Y);
int x = splits[j].x, y = splits[j].y, X = splits[j].X, Y = splits[j].Y;
if (ox < oX && oy < oY)
{
splits[j].empty = true;
// (x, y, X, oy)
if (x < X && y < oy)
{
newsplits.push_back(Window(x, y, X, oy));
}
// (x, oy, ox, oY)
if (x < ox && oy < oY)
{
newsplits.push_back(Window(x, oy, ox, oY));
}
// (oX, oy, X, oY)
if (oX < X && oy < oY)
{
newsplits.push_back(Window(oX, oy, X, oY));
}
// (x, oY, X, Y)
if (x < X && oy < Y)
{
newsplits.push_back(Window(x, oY, X, Y));
}
}
}
int j = 0;
for (int k = 0; k < splits.size() && j < newsplits.size(); ++k)
{
if (splits[k].empty)
{
splits[k].x = newsplits[j].x;
splits[k].X = newsplits[j].X;
splits[k].y = newsplits[j].y;
splits[k].Y = newsplits[j].Y;
splits[k].empty = false;
j++;
}
}
while (j < newsplits.size())
{
splits.push_back(newsplits[j]);
j++;
}
}
int visible = 0;
for (int i = 0; i < splits.size(); ++i)
{
if (!splits[i].empty)
{
visible += (splits[i].X - splits[i].x) * (splits[i].Y - splits[i].y);
}
}
int area = (windows[index].X - windows[index].x) * (windows[index].Y - windows[index].y);
// cout<<"[debug]visible:"<<visible<<", area:"<<area<<endl;
fout.setf(ios::fixed,ios::floatfield);
fout.precision(3);
fout<<visible * 100.0 / area<<endl;
}
}
fin.close();
fout.close();
return 0;
}