Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

继续使用STL set,不过很纠结,G++ RE,C++ AC,大家能帮帮找找原因不?

Posted by yzhw at 2010-02-02 16:27:08 on Problem 1151
# 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator