騫垮憡錛?br />鎴戝仛鐨勪笐闄嬬殑USACO錛屽ぇ瀹跺仛鐨勫悓鏃跺府鎴戝弬鐪嬩互涓嬶紝濡傛灉浣犵殑鏂規(guī)硶姣旀垜濂斤紝鎴栧彂鐜版垜鐨勮В娉曟槸閿欑殑錛屾垨鑰呯湅涓嶆噦鎴戠殑xls閲岄潰鍐欑殑璇濓紝璇峰強(qiáng)鏃跺憡璇夋垜錛屽挨鍏舵槸椹瀺灞辯殑鍚屼粊浠晩銆?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鐨勬爣棰樸婂ぇ璧涘疄璺點(diǎn)嬪彲浠ユ帹嫻嬶細(xì)姣旇禌鐨勪富瑕佸唴瀹瑰氨鏄疍P+鍥捐+鏁版嵁緇撴瀯銆?br />
瀹屾瘯銆?img src ="http://www.shnenglu.com/zyn1996/aggbug/172223.html" width = "1" height = "1" />
]]>
鍏堟槸绱姞錛坸or錛屼竴寮濮嬬湡鍐欐垚+浜嗭紝緇撴灉鏌ヤ簡閭ｄ箞涔呫傘傘傘傦級(jí)
鐒跺悗浣滃樊錛屾劅瑙夌被浼煎崟璋僁P錛屾湁涓綾誨崟璋僁P浣跨敤騫寵 鏍?wèi)鐨勫Q屼絾榪欎釜涓嶉渶瑕佺敤騫寵 鏍?wèi)锛屽彧瑕佺敤tire鏍?wèi)銆?br />鑰冭檻鍒?/1鎬у拰鏈鍧忔儏鍐典笅鏍?wèi)鐨勫瘑闆嗗害锛屼簬鏄啓浜嗛潤鎬佸畬鍏ㄤ簩鍙夋爲(wèi)銆傘傘傘?br />浜庢槸MLE錛岀劧鍚庨檷浣巑axa錛孯T錛屽悓鏃墮檷浣巑axt錛學(xué)A銆?br />鐒跺悗宸﹀彸鏂熼厡鎻愪氦澶氭錛孧LE鎴朩A銆?br />鏈鍚庡崱甯告暟錛屾妸鏍?wèi)鐨勫墠maxt-1灞傜敤bool錛屾渶鍚庝竴灞傜敤int銆傘傘傘傘侫C浜嗐傘傘傘傘?
琚敼孌嬬殑浠ｇ爜
USER:zyn19961
#include
aa[
}]]>