{"id":1399,"date":"2013-03-17T13:17:26","date_gmt":"2013-03-17T05:17:26","guid":{"rendered":"https:\/\/blog.rexdf.org\/?p=1399"},"modified":"2013-03-17T13:17:26","modified_gmt":"2013-03-17T05:17:26","slug":"codeforces-round-172-div-2-rectangle-puzzle","status":"publish","type":"post","link":"https:\/\/blog.rexdf.org\/ja\/2013\/03\/codeforces-round-172-div-2-rectangle-puzzle\/","title":{"rendered":"Codeforces Round #172 (Div. 2)  Rectangle Puzzle"},"content":{"rendered":"<p>&nbsp;<\/p>\n<div>\n<div>C. Rectangle Puzzle<\/div>\n<div>\n<div>time limit per test<\/div>\n<p>2 seconds<\/p><\/div>\n<div>\n<div>memory limit per test<\/div>\n<p>256 megabytes<\/p><\/div>\n<div>\n<div>input<\/div>\n<p>standard input<\/p><\/div>\n<div>\n<div>output<\/div>\n<p>standard output<\/p><\/div>\n<\/div>\n<div>\n<p>You are given two rectangles on a plane. The centers of both rectangles are located in the origin of coordinates (meaning the center of the rectangle&#8217;s symmetry). The first rectangle&#8217;s sides are parallel to the coordinate axes: the length of the side that is parallel to the\u00a0<i>Ox<\/i>axis, equals\u00a0<i>w<\/i>, the length of the side that is parallel to the\u00a0<i>Oy<\/i>\u00a0axis, equals\u00a0<i>h<\/i>. The second rectangle can be obtained by rotating the first rectangle relative to the origin of coordinates by angle\u00a0\u03b1.<\/p>\n<p>&nbsp;<\/p>\n<p><center><img decoding=\"async\" class=\"ls_lazyimg\" alt=\"\" src=\"https:\/\/static.rexdf.org\/plugins\/images-lazyload-and-slideshow\/blank_250x250.gif\" file=\"http:\/\/codeforces.ru\/renderer\/b1330e2845ed392455529db8cd82c60cdd895c9e.png\" \/><noscript><img decoding=\"async\" alt=\"\" src=\"http:\/\/codeforces.ru\/renderer\/b1330e2845ed392455529db8cd82c60cdd895c9e.png\" \/><\/noscript><\/center>&nbsp;<\/p>\n<p>Your task is to find the area of the region which belongs to both given rectangles. This region is shaded in the picture.<\/p>\n<\/div>\n<div>\n<div>Input<\/div>\n<p>The first line contains three integers\u00a0<i>w<\/i>,\u2009<i>h<\/i>,\u2009\u03b1\u00a0(1\u2009\u2264\u2009<i>w<\/i>,\u2009<i>h<\/i>\u2009\u2264\u200910<sup>6<\/sup>;\u00a00\u2009\u2264\u2009\u03b1\u2009\u2264\u2009180). Angle\u00a0\u03b1\u00a0is given in degrees.<\/p>\n<\/div>\n<div>\n<div>Output<\/div>\n<p>In a single line print a real number \u2014 the area of the region which belongs to both given rectangles.<\/p>\n<p>The answer will be considered correct if its relative or absolute error doesn&#8217;t exceed\u00a010<sup>\u2009-\u20096<\/sup>.<\/p>\n<\/div>\n<div>\n<div>Sample test(s)<\/div>\n<div>\n<div>\n<div>input<\/div>\n<pre>1 1 45<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>0.828427125<\/pre>\n<\/div>\n<div>\n<div>input<\/div>\n<pre>6 4 30<\/pre>\n<\/div>\n<div>\n<div>output<\/div>\n<pre>19.668384925<\/pre>\n<\/div>\n<\/div>\n<\/div>\n<div>\n<div>Note<\/div>\n<p>The second sample has been drawn on the picture above.<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"brush: cpp; gutter: true\">\r\n#include &lt;iostream&gt;\r\n#include &lt;cstdio&gt;\r\n#include &lt;cstdlib&gt;\r\n#include &lt;cmath&gt;\r\n#include &lt;iomanip&gt;\r\n\r\nusing namespace std;\r\n\r\nconst double PI=acos(-1);\r\n\r\nint main()\r\n{\r\n    double w,h,a;\r\n    double ans;\r\n    cin&gt;&gt;w&gt;&gt;h&gt;&gt;a;\r\n\r\n    cout&lt;&lt;setiosflags(ios::fixed)&lt;&lt;setprecision(8);\r\n    if(a&gt;90)a=180-a;\r\n    a*=PI\/180;\r\n\r\n    if(fabs(a\/PI*180-90)&lt;1e-5)\r\n    {\r\n        \/\/ans=w*h;\r\n        if(w&gt;h)ans=h*h;\r\n        else ans=w*w;\r\n        cout&lt;&lt;ans;\r\n    }\r\n    else if(a&gt;=atan(2*h\/w) &amp;&amp; w&gt;h\/sin(a)+h\/tan(a))\r\n    {\r\n        ans=h*h\/sin(a);\r\n        cout&lt;&lt;ans;\r\n    }\r\n    else if(a&gt;=atan(2*w\/h) &amp;&amp; h&gt;w\/sin(a)+w\/tan(a))\r\n    {\r\n        ans=w*w\/sin(a);\r\n        cout&lt;&lt;ans;\r\n    }\r\n    else\r\n    {\r\n        ans=w*h;\r\n\r\n\r\n        \/*\r\n        double a11=1.0\/sin(a)\/cos(a)+tan(a)-1.0\/tan(a),\r\n        a12=2\/cos(a),\r\n        a21=2\/cos(a),\r\n        a22=1.0\/sin(a)\/cos(a)+tan(a)-1.0\/tan(a),\r\n        b1=w\/cos(a)+h*tan(a)-w,\r\n        b2=w*tan(a)+h\/cos(a)-h;\r\n        double x1=(b1*a22-b2*a12)\/(a11*a22-a12*a21),x2=(a11*b2-a21*b1)\/(a11*a22-a12*a21);\r\n        ans-=x2*x2\/tan(a)+(w-x2-x1\/sin(a))*(w-x2-x1\/sin(a))*tan(a);\r\n        *\/\r\n        ans=(sin(a\/2)*h*h - 2*cos(a\/2)*h*w + sin(a\/2)*w*w)\/(2*cos(a\/2) - 4*cos(a\/2)*cos(a\/2)*cos(a\/2));\r\n        cout&lt;&lt;ans;\r\n    }\r\n    \/\/system(&quot;pause&quot;);\r\n}\r\n<\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp; C. Rectangle Puzzle time limit pe &hellip; <a href=\"https:\/\/blog.rexdf.org\/ja\/2013\/03\/codeforces-round-172-div-2-rectangle-puzzle\/\">\u7d9a\u304d\u3092\u8aad\u3080 <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[3],"tags":[125],"class_list":["post-1399","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-codeforces"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts\/1399","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/comments?post=1399"}],"version-history":[{"count":0,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/posts\/1399\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/media?parent=1399"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/categories?post=1399"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rexdf.org\/ja\/wp-json\/wp\/v2\/tags?post=1399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}