騫垮憡錛?br />鎴戝仛鐨勪笐闄嬬殑USACO錛屽ぇ瀹跺仛鐨勫悓鏃跺府鎴戝弬鐪嬩互涓嬶紝濡傛灉浣犵殑鏂規硶姣旀垜濂斤紝鎴栧彂鐜版垜鐨勮В娉曟槸閿欑殑錛屾垨鑰呯湅涓嶆噦鎴戠殑xls閲岄潰鍐欑殑璇濓紝璇峰強鏃跺憡璇夋垜錛屽挨鍏舵槸椹瀺灞辯殑鍚屼粊浠晩銆?br />涓嬭澆鍦板潃錛?a >http://dl.dbank.com/c0ecq94jha
]]>
]]>
/*
USER: zyn19961
TASK: window
LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
//
using namespace std;
#define MM(a,i) memset(a,i,sizeof(a))
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
#define PFOR(p,a,next) for(int p=a;p;p=next[p])
//
typedef long long int64;
const int INF=~0U>>2;
//
int maxp=0, minp=0;//maxp鏈鍚庨潰鐨勶紝 minp鏈鍓嶉潰鐨?
class Window{
public:
int x1,y1,x2,y2,pos;
void init(int a, int b, int c, int d){
if(a>c)swap(a,c);if(b>d)swap(b,d);
x1=a,y1=b,x2=c,y2=d,pos=minp--;}
double area(){return (x2-x1)*(y2-y1);}
};
Window window[256];
bool map[300][300];
int hx[50000],hy[50000];
int fx[1000], fy[1000];
double query(char ch){
MM(hx,0),MM(hy,0),MM(fx,0),MM(fy,0);
int fxn=0,fyn=0;
//step 1, 鎵懼嚭鍦╟h鍓嶉潰鐨勭獥鍙?br /> //step 2, 紱繪暎鍖?
FOR(i,0,255)
if(window[i].pos!=-INF)// && i != ch){
if(window[i].pos<=window[ch].pos)
hx[window[i].x1]=true,hx[window[i].x2]=true,
hy[window[i].y1]=true,hy[window[i].y2]=true;
FOR(i,0,32767){
if(hx[i])fx[fxn++]=i,hx[i]=fxn-1;//else hx[i]=-1;
if(hy[i])fy[fyn++]=i,hy[i]=fyn-1;//else hy[i]=-1;
}
//step 3, fillflood
MM(map,false);
FOR(i,0,255)
if(window[i].pos!=-INF&&i!=ch){
if(window[i].pos<window[ch].pos){
int bx=hx[window[i].x1],
by=hy[window[i].y1];
for(int x=bx;fx[x]<window[i].x2; x++)
for(int y=by;fy[y]<window[i].y2;y++)
map[x][y]=true;
}
}
//step 4, 璁＄畻闈㈢Н鐧懼垎姣?
double area=window[ch].area();
int bx=hx[window[ch].x1],
by=hy[window[ch].y1];
double white=0.0;
for(int x=bx;fx[x]<window[ch].x2;x++)
for(int y=by;fy[y]<window[ch].y2;y++){
if(!map[x][y])
white+=(fx[x+1]-fx[x])*(fy[y+1]-fy[y]);
}
return white/area;
}
int main(){
freopen("window.in","r",stdin);
freopen("window.out","w",stdout);
char op, ch;
int x1,y1,x2,y2,cnt=0;
while(scanf("%c",&op) != EOF){
if (op!='s')
scanf("(%c,%d,%d,%d,%d)\n",&ch,&x1,&y1,&x2,&y2);
else
scanf("(%c)\n",&ch);
switch(op){
case 'w': window[ch].init(x1,y1,x2,y2);break;
case 't': window[ch].pos=minp--; break;
case 'b': window[ch].pos=maxp++; break;
case 'd': window[ch].pos=-INF; break;
case 's': printf("%.3f\n", query(ch)*100); break;
default: break;
}
}
return 0;
}
]]>
=绱犳暟鐜?img src ="http://www.shnenglu.com/zyn1996/aggbug/172275.html" width = "1" height = "1" />
]]>
緇撳悎 Charper6鐨勬爣棰樸婂ぇ璧涘疄璺點嬪彲浠ユ帹嫻嬶細姣旇禌鐨勪富瑕佸唴瀹瑰氨鏄疍P+鍥捐+鏁版嵁緇撴瀯銆?br />
瀹屾瘯銆?img src ="http://www.shnenglu.com/zyn1996/aggbug/172223.html" width = "1" height = "1" />
]]>
鍏堟槸绱姞錛坸or錛屼竴寮濮嬬湡鍐欐垚+浜嗭紝緇撴灉鏌ヤ簡閭ｄ箞涔呫傘傘傘傦級
鐒跺悗浣滃樊錛屾劅瑙夌被浼煎崟璋僁P錛屾湁涓綾誨崟璋僁P浣跨敤騫寵 鏍戠殑錛屼絾榪欎釜涓嶉渶瑕佺敤騫寵 鏍戯紝鍙鐢╰ire鏍戙?br />鑰冭檻鍒?/1鎬у拰鏈鍧忔儏鍐典笅鏍戠殑瀵嗛泦搴︼紝浜庢槸鍐欎簡闈欐佸畬鍏ㄤ簩鍙夋爲銆傘傘傘?br />浜庢槸MLE錛岀劧鍚庨檷浣巑axa錛孯T錛屽悓鏃墮檷浣巑axt錛學A銆?br />鐒跺悗宸﹀彸鏂熼厡鎻愪氦澶氭錛孧LE鎴朩A銆?br />鏈鍚庡崱甯告暟錛屾妸鏍戠殑鍓峬axt-1灞傜敤bool錛屾渶鍚庝竴灞傜敤int銆傘傘傘傘侫C浜嗐傘傘傘傘?
琚敼孌嬬殑浠ｇ爜
USER:zyn19961
#include
aa[
}]]>