【计算几何】Oblongs and Right Triangles

题目描述

There are N points on the plane; the i-th point is at (Xi, Yi). There may be multiple points at the same location. Four of the points will be coloured black and three other points will be coloured white. The remaining N − 7 points will be uncoloured.
An oblong is a rectangle that is not a square.
An right triangle is a triangle where one of the interior angles is exactly ninety degrees.
Determine the number of ways to colour the points such that the four black points are the vertices of an oblong and the three white points are the vertices of a right triangle. Note that both shapes should have positive area.

输入

Line 1 contains one integer N (7 ≤ N ≤ 24).
Line 2 contains N integers X1, . . . , XN ( − 229 ≤ Xi ≤ 229).
Line 3 contains N integers Y1, . . . , YN ( − 229 ≤ Yi ≤ 229).

输出

Print one line with one integer, the number of ways to choose an oblong and a right triangle.

样例输入

8
-1 0 0 1 1 1 1 2
0 1 -1 0 -1 -1 -2 -1

样例输出

提示

The only way to form an oblong is with points 1,2,7,8. Of the remaining four points there are two ways to form a right triangle from them.

思路：

首先对于点的排序很重要，我是按照横坐标从小到大，然后纵坐标从小到大拍的，为什么这么排呢，你可以随便画几个矩形，然后以第一个点为第一个直角点，第二、第三为连接一点的直角边，这样总是成立的。

然后就是判三角形和矩形了，矩形是判了三个直角，三角形判任意一个就行，但要注意不能有任何点是重合的，这样用量算一定是零向量

  1 #include <iostream>
  2 #include <bits/stdc++.h>
  3 using namespace std;
  4 typedef long long ll;
  5 struct node
  6 {
  7     ll x,y;
  8     int id;
  9 };
 10 node a[20];
 11 bool vis[20];
 12 int cnt=0,n;
 13 node p[10],q[10];
 14 node fun(node t1,node t2)
 15 {
 16     node temp;
 17     temp.x=t2.x-t1.x;
 18     temp.y=t2.y-t1.y;
 19     return temp;
 20 }
 21 bool len(node t1,node t2)
 22 {
 23     double len1=sqrt(t1.x*t1.x+t1.y*t1.y);
 24     double len2=sqrt(t2.x*t2.x+t2.y*t2.y);
 25     if(len1==len2)
 26         return true;
 27     return false;
 28 }
 29 bool cmp(node t1,node t2)
 30 {
 31     if(t1.x==t2.x)
 32         return t1.y<t2.y;
 33     return t1.x<t2.x;
 34 }
 35 bool judge()///矩形判定
 36 {
 37     node t[10];
 38     for(register int i=1;i<=4;i++)
 39     {
 40         t[i]=q[i];
 41     }
 42     for(register int i=1;i<=3;i++)
 43     {
 44         for(register int j=i+1;j<=4;j++)
 45         {
 46             if(t[i].x==t[j].x&&t[i].y==t[j].y)
 47                 return false;
 48         }
 49     }
 50     sort(t+1,t+1+4,cmp);
 51     node xl1,xl2,xl3,xl4,xl5,xl6;
 52     xl1=fun(t[1],t[2]);
 53     xl2=fun(t[1],t[3]);
 54     ll flag1,flag2,flag3;
 55     flag1=xl1.x*xl2.x+xl1.y*xl2.y;
 56     if(flag1)
 57         return false;
 58     xl3=fun(t[4],t[3]);
 59     xl4=fun(t[4],t[2]);
 60     flag2=xl3.x*xl4.x+xl3.y*xl4.y;
 61     if(flag2)
 62         return false;
 63     xl5=fun(t[2],t[1]);
 64     xl6=fun(t[2],t[4]);
 65     flag3=xl5.x*xl6.x+xl5.y*xl6.y;
 66     if(flag3)
 67         return false;
 68     if(len(xl1,xl2))
 69         return false;
 70     return true;
 71 }
 72 bool check()///三角形判定
 73 {
 74     node xl1,xl2;
 75     for(register int i=1;i<=2;i++)
 76     {
 77         for(register int j=i+1;j<=3;j++)
 78         {
 79             if(p[i].x==p[j].x&&p[i].y==p[j].y)
 80             {
 81                 return false;
 82             }
 83         }
 84     }
 85     xl1=fun(p[1],p[2]);
 86     xl2=fun(p[1],p[3]);
 87     ll flag;
 88     flag=xl1.x*xl2.x+xl1.y*xl2.y;
 89     if(!flag)
 90         return true;
 91     xl1=fun(p[2],p[1]);
 92     xl2=fun(p[2],p[3]);
 93     flag=xl1.x*xl2.x+xl1.y*xl2.y;
 94     if(!flag)
 95         return true;
 96     xl1=fun(p[3],p[1]);
 97     xl2=fun(p[3],p[2]);
 98     flag=xl1.x*xl2.x+xl1.y*xl2.y;
 99     if(!flag)
100         return true;
101     return false;
102 }
103 void dfs1(int step,int x)
104 {
105     if(step==4)
106     {
107         if(check())
108         {
109             cnt++;
110         }
111         return;
112     }
113     for(register int i=x+1;i<=n;i++)
114     {
115         if(vis[i])
116             continue;
117         p[step]=a[i];
118         dfs1(step+1,i);
119     }
120 }
121 void dfs(int step,int x)
122 {
123 
124     if(step==5)
125     {
126         if(judge())
127         {
128             dfs1(1,0);
129         }
130         return;
131     }
132     for(register int i=x+1;i<=n;i++)
133     {
134         q[step]=a[i];
135         vis[i]=1;
136         dfs(step+1,i);
137         vis[i]=0;
138     }
139 }
140 int main()
141 {
142     //freopen("out.txt","w",stdout);
143     scanf("%d",&n);
144     for(register int i=1;i<=n;i++)
145     {
146         scanf("%lld",&a[i].x);
147         a[i].id=i;
148     }
149     for(register int i=1;i<=n;i++)
150     {
151         scanf("%lld",&a[i].y);
152     }
153     sort(a+1,a+1+n,cmp);
154     dfs(1,0);
155     cout << cnt << endl;
156     //cout << "Hello world!" << endl;
157     return 0;
158 }

View Code