CUC-SUMMER-10-C

C - Two Seals
CodeForces - 837C

One very important person has a piece of paper in the form of a rectangle a?×?b.

Also, he has n seals. Each seal leaves an impression on the paper in the form of a rectangle of the size xi?×?yi. Each impression must be parallel to the sides of the piece of paper (but seal can be rotated by 90 degrees).

A very important person wants to choose two different seals and put them two impressions. Each of the selected seals puts exactly one impression. Impressions should not overlap (but they can touch sides), and the total area occupied by them should be the largest possible. What is the largest area that can be occupied by two seals?

Input
The first line contains three integer numbers n, a and b (1?≤?n,?a,?b?≤?100).

Each of the next n lines contain two numbers xi, yi (1?≤?xi,?yi?≤?100).

Output
Print the largest total area that can be occupied by two seals. If you can not select two seals, print 0.

Example
Input
2 2 2
1 2
2 1
Output
4
Input
4 10 9
2 3
1 1
5 10
9 11
Output
56
Input
3 10 10
6 6
7 7
20 5
Output
0

Note
In the first example you can rotate the second seal by 90 degrees. Then put impression of it right under the impression of the first seal. This will occupy all the piece of paper.

In the second example you can't choose the last seal because it doesn't fit. By choosing the first and the third seals you occupy the largest area.

In the third example there is no such pair of seals that they both can fit on a piece of paper.


題意:有一個矩形區(qū)域拙已,你有很多小矩形响迂,選兩個小矩形放到大矩形區(qū)域中,小矩形不重疊夜涕,怎樣選擇使覆蓋面積最大庐镐,求最大面積

解法:四種放法较曼,兩個都正放须尚,兩個都豎放,一正一豎

代碼:

#include<iostream>
#include<stdio.h>
using namespace std;
int x[100],y[100];
int main()
{
    int n,a,b,i,ans=0;
    cin>>n>>a>>b;
    for(i=0;i<n;i++)
        cin>>x[i]>>y[i];
    int xx,yy;
    for(int j=0;j<i;j++){
        for(int k=j+1;k<i;k++){
            xx=x[j]+x[k];
            yy=max(y[j],y[k]);
            if(min(xx,yy)<=min(a,b)&&max(xx,yy)<=max(a,b)){
                ans=max(ans,x[j]*y[j]+x[k]*y[k]);
                continue;
            }
            xx=x[j]+y[k];
            yy=max(y[j],x[k]);
            if(min(xx,yy)<=min(a,b)&&max(xx,yy)<=max(a,b)){
                ans=max(ans,x[j]*y[j]+x[k]*y[k]);
                continue;
            }
            xx=y[j]+x[k];
            yy=max(x[j],y[k]);
            if(min(xx,yy)<=min(a,b)&&max(xx,yy)<=max(a,b)){
                ans=max(ans,x[j]*y[j]+x[k]*y[k]);
                continue;
            }
            xx=y[j]+y[k];
            yy=max(x[j],x[k]);
            if(min(xx,yy)<=min(a,b)&&max(xx,yy)<=max(a,b))
                ans=max(ans,x[j]*y[j]+x[k]*y[k]);
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末假消,一起剝皮案震驚了整個濱河市柠并,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌置谦,老刑警劉巖堂鲤,帶你破解...
    沈念sama閱讀 222,865評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件亿傅,死亡現(xiàn)場離奇詭異媒峡,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)葵擎,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評論 3 399
  • 文/潘曉璐 我一進(jìn)店門谅阿,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人酬滤,你說我怎么就攤上這事签餐。” “怎么了盯串?”我有些...
    開封第一講書人閱讀 169,631評論 0 364
  • 文/不壞的土叔 我叫張陵氯檐,是天一觀的道長。 經(jīng)常有香客問我体捏,道長冠摄,這世上最難降的妖魔是什么糯崎? 我笑而不...
    開封第一講書人閱讀 60,199評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮河泳,結(jié)果婚禮上沃呢,老公的妹妹穿的比我還像新娘。我一直安慰自己拆挥,他們只是感情好薄霜,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,196評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著纸兔,像睡著了一般惰瓜。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上汉矿,一...
    開封第一講書人閱讀 52,793評論 1 314
  • 那天鸵熟,我揣著相機(jī)與錄音,去河邊找鬼负甸。 笑死流强,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的呻待。 我是一名探鬼主播共屈,決...
    沈念sama閱讀 41,221評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼晰筛,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起续室,我...
    開封第一講書人閱讀 40,174評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎炭菌,沒想到半個月后铺浇,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,699評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡敛熬,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,770評論 3 343
  • 正文 我和宋清朗相戀三年肺稀,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片应民。...
    茶點(diǎn)故事閱讀 40,918評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡话原,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出诲锹,到底是詐尸還是另有隱情繁仁,我是刑警寧澤,帶...
    沈念sama閱讀 36,573評論 5 351
  • 正文 年R本政府宣布归园,位于F島的核電站黄虱,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏庸诱。R本人自食惡果不足惜捻浦,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,255評論 3 336
  • 文/蒙蒙 一盐捷、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧默勾,春花似錦碉渡、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,749評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至环疼,卻和暖如春习霹,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背炫隶。 一陣腳步聲響...
    開封第一講書人閱讀 33,862評論 1 274
  • 我被黑心中介騙來泰國打工淋叶, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人伪阶。 一個月前我還...
    沈念sama閱讀 49,364評論 3 379
  • 正文 我出身青樓煞檩,卻偏偏與公主長得像,于是被迫代替她去往敵國和親栅贴。 傳聞我的和親對象是個殘疾皇子斟湃,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,926評論 2 361

推薦閱讀更多精彩內(nèi)容