Problem C. Equivalent Cards

題目連接：

http://www.codeforces.com/gym/100253

Description

Jane is playing a game with her friends. They have a deck of round cards of radius 100. Each card has a
set of disjoint rectangles strictly within the bounding circle. The rectangles' vertices and the card center
have integer coordinates. However, the rectangles' edges are not necessarily parallel to the axes. The value
of a card depends on the rectangles in it and equals the sum of areas of all its rectangles. The cards are
equivalent if they have same values.
The rules are simple. Each player is given a card in the beginning. Then they turn the cards face-up. If
any player can spot another player's card equivalent to their own card, the player who rst noticed the
equivalency gives their cards to another player and draws a new card from the deck face-up. The game
ends when there are no equivalent cards among players, or when a player needs to draw a card, but the
deck is empty. The player with the least number of cards wins.
Of course, Jane never cheats. She also believes that her friends don't cheat as well. But the game is so
dynamic, that there is no time to verify if some cards are equivalent, i.e. have the same total area of
rectangles. So, if somebody makes a mistake and claims that two cards are equivalent while they are not,
other players may leave it unnoticed and keep playing.
To avoid this, Jane decided to use her web-camera and write a program to nd equivalent cards. She noticed
that cards on the pictures from the camera taken under some angle look like ellipses and rectangles look
like parallelograms, but she is not good at geometry. Also the images are scaled, shifted and rotated, so
the problem seems to be too hard to Jane. She asked you to write an algorithm to nd equivalent cards.
Fortunately, you know a good image processing library which does the hardest work of nding gures for
you. Your task is, given the library output, nd all equivalence classes and for each card tell which class
it belongs to. An equivalence class is a set of cards having the same sum of areas of rectangles.

Input

The rst line of the input contains n (1 ≤ n ≤ 100), where n is the number of pictures. Each picture
contains a single card in it.
Then n descriptions of pictures follow. The description of a picture consists of several lines. The rst
two lines of the description specify an ellipse a card boundary on the picture. The rst line contains
coordinates of two most distant opposite points on the ellipse (any pair of opposite points in case of a
tie). The second line contains the coordinates of two closest opposite points on the ellipse (any pair of
opposite points in case of a tie), the distance between them is at least 1. These four points completely
determine the ellipse. The following line contains ri (1 ≤ ri ≤ 4) the number of rectangles on the card.
The following ri blocks contain the coordinates of four points, a pair of coordinates per line. Each point
is a corner of a corresponding parallelogram on the picture in the clockwise or counter-clockwise order.
All coordinates are oating point numbers between -1000 and 1000, inclusively. They are given with an
accuracy of exactly 8 digits after the decimal point

Output

Print the only line containing the sequence f1, f2, . . . , fn describing the equivalence classes. It should be
true that fi = fj if and only if the i-th and the j-th cards are equivalent. You may use any integer values
between 1 and 100 inclusive.

Sample Input

3
-10.00000000 0.00000000 10.00000000 0.00000000
0.00000000 -10.00000000 0.00000000 10.00000000
2
5.00000000 5.00000000
5.00000000 6.00000000
6.00000000 6.00000000
6.00000000 5.00000000
3.00000000 2.00000000
3.00000000 1.00000000
4.00000000 1.00000000
4.00000000 2.00000000
-8.00000000 -6.00000000 8.00000000 6.00000000
6.00000000 8.00000000 -6.00000000 -8.00000000
1
1.00000000 0.00000000
0.00000000 1.00000000
-1.00000000 0.00000000
0.00000000 -1.00000000
-10.00000000 0.00000000 10.00000000 0.00000000
0.00000000 -5.00000000 0.00000000 5.00000000
1
1.00000000 1.00000000
0.00000000 1.00000000
0.00000000 -1.00000000
1.00000000 -1.00000000

Sample Output

1 1 2

Hint

題意

說平面上有一個圓，圓內有很多正方形，現在這個圓被拉伸成為了一個橢圓，里面的正方形就被拉成了平行四邊形。

現在問你按照面積和分類，這些圓能夠分成幾類

題解：

橢圓面積為piab，平行四邊形面積為ab，所以兩個圖形是等比例放縮的，那就直接按照比例算就好了……

代碼

#include<bits/stdc++.h> using namespace std; const double INF = 1E200 ; const double EP = 1E-10 ; const int MAXV = 300 ; const double PI = 3.14159265 ; /* 基本幾何結構 */ struct POINT {double x;double y;POINT(double a=0, double b=0) { x=a; y=b;} //constructor }; struct LINESEG {POINT s;POINT e;LINESEG(POINT a, POINT b) { s=a; e=b;}LINESEG() { } }; struct LINE // 直線的解析方程 a*x+b*y+c=0 為統一表示，約定 a >= 0 {double a;double b;double c;LINE(double d1=1, double d2=-1, double d3=0) {a=d1; b=d2; c=d3;} }; LINE makeline(POINT p1,POINT p2) {LINE tl;int sign = 1;tl.a=p2.y-p1.y;if(tl.a<0){sign = -1;tl.a=sign*tl.a;}tl.b=sign*(p1.x-p2.x);tl.c=sign*(p1.y*p2.x-p1.x*p2.y);return tl; } bool lineintersect(LINE l1,LINE l2,POINT &p) // 是 L1，L2 {double d=l1.a*l2.b-l2.a*l1.b;if(abs(d)<EP) // 不相交return false;p.x = (l2.c*l1.b-l1.c*l2.b)/d;p.y = (l2.a*l1.c-l1.a*l2.c)/d;return true; } /* r=dotmultiply(p1,p2,op),得到矢量(p1-op)和(p2-op)的點積，如果兩個矢量都非零矢量 r<0：兩矢量夾角為鈍角； r=0：兩矢量夾角為直角； r>0：兩矢量夾角為銳角 *******************************************************************************/ double dist(POINT p1,POINT p2) // 返回兩點之間歐氏距離 {return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) ); } double multiply(POINT sp,POINT ep,POINT op) {return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); } double dotmultiply(POINT p1,POINT p2,POINT p0) {return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y)); } double relation(POINT p,LINESEG l) {LINESEG tl;tl.s=l.s;tl.e=p;return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e)); } // 求點C到線段AB所在直線的垂足 P POINT perpendicular(POINT p,LINESEG l) {LINE l1=makeline(l.s,l.e);LINE l2=l1;l2.c=-(l1.a*p.x+l2.b*p.y); } double dis(POINT A,POINT B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); } double solve() {POINT p1,p2,p3,p4,P[4],mid;double ans=0;scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);scanf("%lf%lf%lf%lf",&p3.x,&p3.y,&p4.x,&p4.y);mid.x=(p1.x+p2.x)/2.0,mid.y=(p1.y+p2.y)/2.0;double tmp=dist(p1,p2)*dist(p3,p4);int q;scanf("%d",&q);for(int i=0;i<q;i++){for(int i=0;i<4;i++)scanf("%lf%lf",&P[i].x,&P[i].y);ans+=abs(multiply(P[0],P[2],P[1]));}return ans/tmp; } double area[5000]; int Ans[5005]; int main() {int t;scanf("%d",&t);for(int i=1;i<=t;i++){Ans[i]=i;area[i]=solve();}for(int i=1;i<=t;i++){for(int j=1;j<i;j++){if(abs(area[i]-area[j])<1e-6){Ans[i]=Ans[j];break;}}}for(int i=1;i<=t;i++){if(i==1)printf("%d",Ans[i]);else printf(" %d",Ans[i]);}printf("\n");return 0; }

轉載于:https://www.cnblogs.com/qscqesze/p/5775227.html

總結

以上是生活随笔為你收集整理的2013-2014 ACM-ICPC, NEERC, Southern Subregional Contest Problem C. Equivalent Cards 计算几何的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。