hdu--6055--Regular polygon

心已赠人 2022-06-11 02:25 105阅读 0赞

# Regular polygon #

**Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)  
Total Submission(s): 891    Accepted Submission(s): 326**

Problem Description

On a two-dimensional plane, give you n integer points. Your task is to figure out how many different regular polygon these points can make.

Input

The input file consists of several test cases. Each case the first line is a numbers N (N <= 500). The next N lines ,each line contain two number Xi and Yi(-100 <= xi,yi <= 100), means the points’ position.(the data assures no two points share the same position.)

Output

For each case, output a number means how many different regular polygon these points can make.

Sample Input

4
    0 0
    0 1
    1 0
    1 1
    6
    0 0
    0 1
    1 0
    1 1
    2 0
    2 1

Sample Output

1
    2

Source

[2017 Multi-University Training Contest - Team 2][]

官方题解：

题意，二维平面上给N个整数点，问能构成多少个不同的正多边形。 题解：容易得知只有正四边形可以使得所有的顶点为整数点。（具体证明可参考杨景钦在2017的国家队论文） 所以正解即求出所有的正四边形个数。 枚举2个点，然后暴力判断另外2个点的位置是否存在。 复杂度 N\*N\*logN。

我的思路：

因为组成的形状只有正方形，可以先找到正方形的一个边，根据组成这条边的两个端点，推出可以和他们可以组成正方形的点（这条线的两边都要考虑），如果这两个点在给出的点中，ans就加加； 因为数据量很小，直接枚举就好啦 枚举两个点，算出他们的向量，然后去查找是否存在组成正方形的点， 结果除8 代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&lt;stdio.h&gt; 
 
 #include&lt;algorithm&gt; 
 
 #include&lt;string.h&gt; 
 
 int&nbsp;aim[ 
 500][ 
 500]; 
 
 struct&nbsp;Point 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x,y; 
 }p[ 
 555]; 
 
 int&nbsp;solve(Point&nbsp;a,Point&nbsp;b) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x=a.x-b.x; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;y=a.y-b.y; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;ans= 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///查找这条边的一侧 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(a.x+y&gt;= 
 0&amp;&amp;a.y-x&gt;= 
 0&amp;&amp;b.x+y&gt;= 
 0&amp;&amp;b.y-x&gt;= 
 0&amp;&amp;aim[a.x+y][a.y-x]&amp;&amp;aim[b.x+y][b.y-x]) 
 &nbsp;&nbsp;&nbsp;&nbsp;ans++; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///查找这条边的另一侧 &nbsp;&nbsp;&nbsp;&nbsp; 
 if(a.x-y&gt;= 
 0&amp;&amp;a.y+x&gt;= 
 0&amp;&amp;b.x-y&gt;= 
 0&amp;&amp;b.y+x&gt;= 
 0&amp;&amp;aim[a.x-y][a.y+x]&amp;&amp;aim[b.x-y][b.y+x]) 
 &nbsp;&nbsp;&nbsp;&nbsp;ans++; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;ans; 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(scanf( 
 "%d",&amp;n)== 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(aim, 
 0, 
 sizeof(aim)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 0;i&lt;n;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;a,b; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d%d",&amp;a,&amp;b); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a+= 
 100;b+= 
 100; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[i].x=a; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p[i].y=b; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;aim[a][b]= 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;ans= 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 0;i&lt;n;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 0;j&lt;n;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(i!=j) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans+=solve(p[i],p[j]); 
 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%d\n",ans/ 
 8); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

[2017 Multi-University Training Contest - Team 2]: http://acm.hdu.edu.cn/search.php?field=problem&key=2017+Multi-University+Training+Contest+-+Team+2&source=1&searchmode=source