URAL 2036 Intersect Until You're Sick of It 形成点的个数 next

A - Intersect Until You're Sick of It

Time Limit:500MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit Status Practice URAL 2036

Description

Ural contests usually contain a lot of geometry problems. Many participants do not conceal their discontent with such disbalance. Still, we have decided not to break the tradition and give you an unbalanced contest. Let’s start!

Consider an iterative process for a set of points on a plane. Every iteration consists of three steps:

Draw a line through every pair of different points.
Find all intersections of all pairs of different non-parallel lines.
Merge the initial set of points with the set of intersection points and go to step one.

After each iteration, the number of points either increases or stays the same.

You are given a set of points. Iterations repeat while the number of points increases. How many points will be in the set after the end of this iterative process?

Input

The first line contains an integer n (1 ≤ n ≤ 100000). Further input describes n different points. For every point, you are given a pair of integer coordinates whose absolute value does not exceed 10 ⁸.

Output

If the process is infinite, print “oo” (two lowercase Latin letters ‘o’), otherwise print the number of points in the set after the end of the process.

Sample Input

input	output
4 0 0 0 1 1 0 1 1

题意：给你n个不同的点，第一步，将任意两个点之间连成一条直线，第二步，直线相交可以形成新的点，然后再重复第一步，

问最后可以形成多少个点，如果无穷多个输出oo;

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <cstring>

#include <cstring>

#include <algorithm>

using namespace std;

typedef  long long  ll;

typedef unsigned long long ull;

#define MM(a,b) memset(a,b,sizeof(a));

#define inf 0x7f7f7f7f

#define FOR(i,n) for(int i=1;i<=n;i++)

#define CT continue;

#define PF printf

#define SC scanf

const int mod=1000000007;

const int N=1e5+10;

struct Point{

  ll x,y;

  void read(){

      scanf("%lld%lld",&x,&y);}

  bool operator<(const Point &a) const{

      if(this->x!=a.x)  return this->x<a.x;

      else return this->y<a.y;

  }

}p[N];

Point operator-(Point a,Point b)

{

    return (Point){a.x-b.x,a.y-b.y};

}

ll det(Point a,Point b)

{

   return a.x*b.y-b.x*a.y;

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++) p[i].read();

    if(n<=3) {printf("%d\n",n);return 0;}

    sort(p+1,p+n+1);

    if(n==4)

    {

        do

        {

            if(det(p[2]-p[1],p[4]-p[3])==0&&det(p[1]-p[4],p[2]-p[3])==0

            &&det(p[3]-p[1],p[2]-p[1])!=0)

            {printf("5\n");return 0;};

        }while(next_permutation(p+1,p+n+1));

    }

    if(n==5)

    {

        do

        {

            if(det(p[2]-p[1],p[4]-p[3])==0&&det(p[1]-p[4],p[2]-p[3])==0&&

               det(p[3]-p[1],p[2]-p[1])!=0&&det(p[4]-p[5],p[2]-p[5])==0&&

               det(p[3]-p[5],p[1]-p[5])==0)

            {printf("5\n");return 0;};

        }while(next_permutation(p+1,p+n+1));

    }

    for(int i=1;i<=2;i++)

    for(int j=i+1;j<=4;j++)

    {

        int cnt=2;

        for(int k=1;k<=n;k++) if(k!=i&&k!=j)

           if(det(p[k]-p[i],p[k]-p[j])==0) cnt++;

        if(cnt>=n-1) {printf("%d\n",n);return 0;}

    }

    printf("oo\n");

    return 0;

}

　比赛分析：比赛时看到计算几何的题都不敢想，，，，比赛完了后稍微看了下题解，自己再想了想，发现水的一笔；

分析：看到题目时被吓到了，觉得情况好多，，心态很重要！

假设<=3个点，那么自己无论怎么排列，都不会形成新的点，所以就输出n；

如果是4个点，如果是平行四边形，，那么只能形成5个点；

如果是五个点，如果在是平行四边形的基础上，第五个点位于平行四边形的对角线上，那么最后也是五个点。

最后一个是比较特殊的情况，有n个点，假如n-1个点共线，一个点在直线外，那么答案就是n，但是

如果在直线外的点的个数>=2的话，那么就是oo了。

最后，因为要求点的全排列，需要用到next_permutation()函数：

1.因为point是自定义结构体，所以要定义点的优先级

2.next_permutation()函数使用前需要先对待排列数组排下序，利用sort从小到大排序

巴特西

URAL 2036 Intersect Until You're Sick of It 形成点的个数 next_permutation（）函数

最新文章

热门文章