CodeForces 135 B. Rectangle and Square（判断正方形和 矩形）

题目：http://codeforces.com/problemset/problem/135/B

题意：给8个点 判断能否用 4个点构成正方形，另外4个点构成 矩形。

输出 第一行是正方形 ，第二行是矩形。

我的思路：用了4个for循环 枚举四个点， 用向量判断，四个点构成 六条边，如果这六条边里，

有四条边 与他们垂直的边有两个，就说明是矩形，在这个基础上，有 2条边 与他们垂直的边有一个。

说明是正方形。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

struct point
{
    int x,y;
} p[10];
int check(point a,point b,point c,point d)
{
    int i,j,sumt=0,sumo=0;
    int px[10],py[10];//代表6条边的 向量
    int y[10];
    memset(y,0,sizeof(y));
    px[1]=a.x-b.x;
    py[1]=a.y-b.y;
    px[2]=a.x-c.x;
    py[2]=a.y-c.y;
    px[3]=a.x-d.x;
    py[3]=a.y-d.y;
    px[4]=b.x-c.x;
    py[4]=b.y-c.y;
    px[5]=b.x-d.x;
    py[5]=b.y-d.y;
    px[6]=c.x-d.x;
    py[6]=c.y-d.y;
    for(i=1; i<=6; i++)
    {
        for(j=i+1; j<=6; j++)
            if((px[i]*px[j]+py[i]*py[j])==0)//判断垂直
            {
                y[i]++;
                y[j]++;
            }
    }
    for(i=1; i<=6; i++)
    {
        if(y[i]==2)
            sumt++;//有2条边 与其垂直的个数
        if(y[i]==1)
            sumo++;//有1条边 与其垂直的个数
    }
    if(sumt==4&&sumo==2)
        return 2;// 是正方形
    if(sumt==4)
        return 1;//是 矩形
    return 0;//都不是
}
int main()
{
    int i,j,k,l,ans,f,m;
    int i2,j2,k2,l2;
    int b[10],y;
    while(cin>>p[1].x>>p[1].y)
    {
        f=0;
        for(i=2; i<=8; i++)
            cin>>p[i].x>>p[i].y;
        for(i=1; i<=5; i++)
        {
            for(j=i+1; j<=6; j++)
            {
                for(k=j+1; k<=7; k++)
                {
                    for(l=k+1; l<=8; l++)
                    {
                        ans=check(p[i],p[j],p[k],p[l]);
                        if(ans==0)
                            continue;
                        if(ans==2)//当前是正方形时
                        {
                            y=1;
                            for(m=1; m<=8; m++)
                            {
                                if(m!=i&&m!=j&&m!=k&&m!=l)
                                    b[y++]=m;
                            }
                            i2=b[1];
                            j2=b[2];
                            k2=b[3];
                            l2=b[4];

                            ans=check(p[i2],p[j2],p[k2],p[l2]);//看是否 剩下的点是矩形
                            if(ans)
                            {
                                f=1;
                                break;
                            }
                        }
                    }
                    if(f)
                    break;
                }
                if(f)  break;
            }
            if(f)  break;
        }
        if(f)
        {
            cout<<"YES"<<endl;
            printf("%d %d %d %d
",i,j,k,l);
            printf("%d %d %d %d
",i2,j2,k2,l2);
        }
        else
            cout<<"NO"<<endl;
    }
    return 0;
}