多邊形凸包。。。。
Board Wrapping Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu
Submit Status
Description
Problem B
Board Wrapping
Input: standard input
Output: standard output
Time Limit: 2 seconds
The small sawmill in Mission, British Columbia, has develZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcGVkIGEgYnJhbmQgbmV3IHdheSBvZiBwYWNrYWdpbmcgYm9hcmRzIGZvciBkcnlpbmcuIEJ5IGZpeGF0aW5nIHRoZSBib2FyZHMgaW4gc3BlY2lhbCBtb3VsZHMsIHRoZSBib2FyZCBjYW4gZHJ5IGVmZmljaWVudGx5IGluIGEgZHJ5aW5nIHJvb20uPC9wPgo8cD5TcGFjZSBpcyBhbiBpc3N1ZSB0aG91Z2guIFRoZSBib2FyZHMgY2Fubm90IGJlIHRvbyBjbG9zZSwgYmVjYXVzZSB0aGVuIHRoZSBkcnlpbmcgd2lsbCBiZSB0b28gc2xvdy4gT24gdGhlIG90aGVyIGhhbmQsIG9uZSB3YW50cyB0byB1c2UgdGhlIGRyeWluZyByb29tIGVmZmljaWVudGx5LjwvcD4KPHA+TG9va2luZyBhdCBpdCBmcm9tIGEgPHN0cm9uZz4yLUQ8L3N0cm9uZz4gcGVyc3BlY3RpdmUsIHlvdXIgdGFzayBpcyB0byBjYWxjdWxhdGUgdGhlIGZyYWN0aW9uIGJldHdlZW4gdGhlIHNwYWNlIG9jY3VwaWVkIGJ5IHRoZSBib2FyZHMgdG8gdGhlIHRvdGFsIHNwYWNlIG9jY3VwaWVkIGJ5IHRoZSBtb3VsZC4gTm93LCB0aGUgbW91bGQgaXMgc3Vycm91bmRlZCBieSBhbiBhbHVtaW5pdW0gZnJhbWUgb2YgbmVnbGlnaWJsZSB0aGlja25lc3MsIGZvbGxvd2luZwogdGhlIGh1bGwgb2YgdGhlIGJvYXJkcw==" corners tightly. The space occupied by the mould would thus be the interior of the frame.
On the first line of input there is one integer, N <= 50, giving the number of test cases (moulds) in the input. After this line, N test cases follow. Each test case starts with a line containing one integer n, 1< n <= 600, which is the number of boards in the mould. Then n lines follow, each with five floating point numbers x, y, w, h, j where 0 <= x, y, w, h <=10000 and –90° < j <=90°. The x and y are the coordinates of the center of the board and w and h are the width and height of the board, respectively. j is the angle between the height axis of the board to the y-axis in degrees, positive clockwise. That is, if j = 0, the projection of the board on the x-axis would be w. Of course, the boards cannot intersect.
For every test case, output one line containing the fraction of the space occupied by the boards to the total space in percent. Your output should have one decimal digit and be followed by a space and a percent sign (%).
1
4
4 7.5 6 3 0
8 11.5 6 3 0
9.5 6 6 3 90
4.5 3 4.4721 2.2361 26.565
64.3 %
Swedish National Contest
The Sample Input and Sample Output corresponds to the givenpicture
Source
Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: (Computational) Geometry :: Polygon :: StandardSubmit Status
#include#include #include #include #include #include using namespace std; const double eps=1e-6; int dcmp(double x) { if(fabs(x) vp,ch; // 點集凸包 // 如果不希望在凸包的邊上有輸入點,把兩個 <= 改成 < // 注意:輸入點集會被修改 vector CovexHull(vector & p) { sort(p.begin(),p.end()); p.erase(unique(p.begin(),p.end()),p.end()); int n=p.size(); int m=0; vector ch(n+1); for(int i=0;i 1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-2;i>=0;i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--; ch[m++]=p[i]; } if(n>1) m--; ch.resize(m); return ch; } double PolygonArea(vector & p) { int n=p.size(); double area=0; for(int i=1;i