首页 > 代码库 > HDU 5020 容器标记斜率

HDU 5020 容器标记斜率

题意:给你n个点,让你求出三点共线的最大情况,   点数为1000个

题解:很显然 ,点数1000,普通枚举O(n3),肯定过不了了。

方法为map记录每个点和其他点连线的斜率,如果斜率出现次数大于2 ,Num += C(N,2);

代码:

#include<stdio.h>
#include<iostream>
#include<map>
using namespace std;
map<double , int> mark;
int flag;
struct Node
{
   int x, y;       
}cun[1005];
void slove(Node a, Node b)
{
   if (a.x == b.x)  {flag ++ ;return ;}
   double k =(1.0 * (a.y - b.y)) / (1.0 * (a.x - b.x));  
   mark[k] ++;
   return ;   
}
int slov(int a)
{
   int k = a * (a-1) / 2;
   return  k;       
} 
int main()
{
    int t, n;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d", &n);
       mark.clear();
       for(int i = 0; i < n; i++)
       {
         scanf("%d%d", &cun[i].x, &cun[i].y);        
       }
       __int64 num = 0;
       flag = 0;
       for(int i = 0; i < n; i++)
       {
         for(int j = i+1; j < n; j++)
         {
            slove (cun[i], cun[j]);    
         }  
         map<double, int>::iterator my_Itr;
         for(my_Itr=mark.begin();my_Itr!=mark.end();++my_Itr)
         {
            int k = my_Itr->second;
            if(k >= 2) 
              num += slov(k);
         }     
         if(flag >= 2)
         num += slov(flag);
         flag = 0;
         mark.clear();
       }  
       printf("%I64d\n", num);      
    }   
}

HDU 5020 容器标记斜率