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
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

如果用薛矛大牛的术语说应该属于矩形切割。。。。

Posted by yzhw at 2009-09-24 23:23:09 on Problem 3277
In Reply To:用矩形扫描线+STL SET写了个,跑了1S,汗。。。 Posted by:yzhw at 2009-09-24 21:41:18
> Source Code
> 
> Problem: 3277  User: yzhw 
> Memory: 5020K  Time: 938MS 
> Language: G++  Result: Accepted 
> 
> Source Code 
> # include <iostream>
> using namespace std;
> # include <set>
> # include <cstdio>
> # include <cstdlib>
> struct line
> {
>     int id;
>     long long x;
>     bool sta;
> };
> struct node
> {
>    long long p;
>    int count;
> };
> class cmp1
> {
> public:
>        bool operator()(node a,node b) const
>        {
>             return a.p>b.p;
>        }
> };
>             
> line data[100000];
> long long h[100000];
> int cmp(const void *a,const void *b)
> {
>     line *aa=(line *)a;
>     line *bb=(line *)b;
>     return aa->x-bb->x;
> }
> set<node,cmp1> res;
> int main()
> {
>     int num;
>     scanf("%d",&num);
>     for(int i=1;i<=num;i++)
>     {
>        scanf("%lld %lld %lld",&data[2*i-1].x,&data[2*i].x,&h[i]);
>        data[2*i-1].id=data[2*i].id=i;
>        data[2*i-1].sta=1;
>        data[2*i].sta=0;
>     }
>     qsort(data+1,2*num,sizeof(line),cmp); 
>     long long total=0;
>     for(int i=1;i<2*num;i++)
>     {
>        if(data[i].sta)
>        {
>          node temp;
>          temp.count=1;
>          temp.p=h[data[i].id];
>          set<node,cmp1>::iterator it=res.find(temp);
>          if(it==res.end())
>             res.insert(temp);
>          else
>          {
>              temp=*it;
>              temp.count++;
>              res.erase(temp);
>              res.insert(temp);
>          }
>        }
>        else
>        {
>          node temp;
>          temp.count=1;
>          temp.p=h[data[i].id];
>          set<node,cmp1>::iterator it=res.find(temp);
>          if(it->count==1)
>            res.erase(temp);
>          else
>          {
>             temp=*it;
>             temp.count--;
>             res.erase(temp);
>             res.insert(temp);
>          }
>        }
> 	   if(data[i].x==data[i+1].x||res.empty()) continue;
>        total+=(data[i+1].x-data[i].x)*(res.begin()->p);
>     }
>     printf("%lld\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