Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
继续使用STL set,不过很纠结,G++ RE,C++ AC,大家能帮帮找找原因不?# include <iostream> # include <set> # include <cmath> # include <algorithm> # include <cstdio> using namespace std; struct rec { int id; double l,r,u,b; }data[101]; struct line { int id; double p; bool f; }tmp[201]; bool cmp(const line a,const line b) { if(abs(a.p-b.p)>1e-8) return a.p<b.p; else { if(a.f) return true; else return false; } } struct cmp1 { bool operator()(const rec a,const rec b) const { if(abs(a.b-b.b)>1e-8) return a.b<b.b; else return a.id<b.id; } }; int main() { int num; int c=1; while(true) { cin>>num; if(!num) break; printf("Test case #%d\n",c++); set<rec,cmp1> l; for(int i=1;i<=num;i++) { cin>>data[i].l>>data[i].b>>data[i].r>>data[i].u; data[i].id=i; tmp[2*i-1].id=i; tmp[2*i].id=i; tmp[2*i-1].f=true; tmp[2*i].f=false; tmp[2*i-1].p=data[i].l; tmp[2*i].p=data[i].r; } sort(tmp+1,tmp+1+num*2,cmp); double last=tmp[1].p; double total=0; for(int i=1;i<=2*num;i++) { if(abs(tmp[i].p-last)>1e-8) { double length=0; double di=l.begin()->b,ding=l.begin()->u; for(set<rec,cmp1>::iterator it=l.begin();it!=l.end();it++) { if(it->b<=ding+1e-8) { ding=max(ding,it->u); } else { length+=ding-di; ding=it->u; di=it->b; } } length+=ding-di; total+=length*(tmp[i].p-last); last=tmp[i].p; } if(tmp[i].f) { l.insert(data[tmp[i].id]); } else l.erase(data[tmp[i].id]); } printf("Total explored area: %.2f\n\n",total); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator