cfgym100253C

201708 （ACM）几何

题意

• n张圆形卡片，半径100。卡片上画有矩形，个数不超过四个，并且顶点都是整点。如果两张卡片上的矩形面积和相等，则认为这两张卡片相等。
• 用相机拍摄卡片，照片上的圆形变形成椭圆，矩形变形成平行四边形。给出变形后的图形信息。
  
  • 输入：椭圆距离最远和最近的两组点。平行四边形四个点坐标。
• 对于输入的卡片分类，每一类中所有卡片都两两相等。

题解

• 椭圆面积：$pi*a*b$
• 平行四边形面积：假设平行四边形四个顶点是ABCD，则$S=\textbf{BA}×\textbf{BC}$（向量叉积）
• 那么比对两个卡片的$S/(a*b)$的值，如果相等就用并查集连接，最后只要输出每个点属于哪个集合即可。

注意

• 卡精度。
• 但是题目保证了[圆半径100，矩形顶点都在整点]，所以只要[eps小于1/40000，并且直接对比例进行比较]就没问题。

代码

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define sz(a) (int)a.size()
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<" = "<<a<<endl
#define x(a) a.x
#define y(a) a.y
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
//----
const int N=105;
const db eps=1e-5;
int sign(db x) {
    return (x>eps)-(x<-eps);
}
int n;
int pre[N];
db x[N],y[N],z[N];
struct P {
    db x,y;
    P() {}
    P(db x, db y) {
        this -> x = x;
        this -> y = y;
    }
    P operator + (const P &c) const {
        return P(x + c.x, y + c.y);
    }
    P operator - (const P &c) const {
        return P(x - c.x, y - c.y);
    }
};
struct S {
    int r;
    P a[2],b[2],c[6][6];
}ss[N];
P read() {
    db x,y;scanf("%lf%lf",&x,&y);
    return P(x,y);
}
db abs(P a) {
    return sqrt(x(a) * x(a) + y(a) * y(a));
}
db cross(P a, P b) {
    return x(a) * y(b) - x(b) * y(a);
}
int find(int x) {
    if(x==pre[x]) return x;
    return pre[x]=find(pre[x]);
}
void join(int x,int y) {
    int fx=find(x),fy=find(y);
    pre[fx]=fy;
}
void gao(int u) {
    S &t = ss[u];
    db a=abs(t.a[0]-t.a[1]);
    db b=abs(t.b[0]-t.b[1]);
    y[u]=a*b;
    rep(i,0,t.r) {
        x[u]=x[u]+fabs(cross(t.c[i][0]-t.c[i][1], t.c[i][2]-t.c[i][1]));
    }
    z[u]=x[u]/y[u];
}
bool eq(int u,int v) {
    return sign(z[u]-z[v])==0;
}
int main(){
    ///
    scanf("%d",&n);
    ///init
    rep(i,0,n+1) pre[i]=i;
    ///read
    rep(i,1,n+1) {
        ss[i].a[0]=read();
        ss[i].a[1]=read();
        ss[i].b[0]=read();
        ss[i].b[1]=read();
        scanf("%d",&ss[i].r);
        rep(j,0,ss[i].r) {
            rep(k,0,4) {
                ss[i].c[j][k]=read();
            }
        }
    }
    ///solve
    rep(i,1,n+1) gao(i);
    rep(i,1,n+1) {
        rep(j,i+1,n+1) {
            if(eq(i,j)) join(i,j);
        }
    }
    ///print
    rep(i,1,n+1) printf("%d%c",find(i),(i==n)?'\n':' ');
    return 0;
}