UVA270-Lining Up-白红宇

UVA270-Lining Up

阅读量：5097 次

发布时间：2019-06-13

本文共 2411 字，大约阅读时间需要 8 分钟。

斜率斜率斜率.........

#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;struct node{ int x,y; node(){} node(int a,int b){x=a;y=b;}};int main(){ // freopen("in","r",stdin); vector
            
             box; map
             
              dir; string s; int T,i,j,k,n,x,y,ans,t; cin>>T; getchar(); getchar(); for(i=0;i

Time Limit:3000MS

Memory Limit:Unknown

64bit IO Format:%lld & %llu

Description

``How am I ever going to solve this problem?

" said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?

Your program has to be efficient!

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The output consists of one integer representing the largest number of points that all lie on one line.

11 12 23 39 1010 11

Source

Root :: Competitive Programming: Increasing the Lower Bound of Programming Contests (Steven & Felix Halim) :: Chapter 7. (Computational) Geometry :: Geometry Basics ::

Root :: AOAPC I: Beginning Algorithm Contests (Rujia Liu) ::

Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: More Advanced Topics :: Problem Decomposition ::

Root :: Competitive Programming 2: This increases the lower bound of Programming Contests. Again (Steven & Felix Halim) :: (Computational) Geometry :: Basic Geometry ::

转载于:https://www.cnblogs.com/cxchanpin/p/7287307.html

你可能感兴趣的文章