B
Brickie_liu

## 题目描述

Given points on a 2D plane, judge whether there’re three points that locate on the same line.

## 输入格式

The number of test cases T(1≤T≤10) appears in the first line of input.

Each test case begins with the number of points N(1≤N≤100). The following N lines describe the coordinates (xi,yi) of each point, in accuracy of at most 3 decimals. Coordinates are ranged in [−104,104].

## 输出格式

For each test case, output Yes if there’re three points located on the same line, otherwise output No.

2
3
0.0 0.0
1.0 1.0
2.0 2.0
3
0.001 -2.000
3.333 4.444
1.010 2.528

Yes
No

## 通过代码

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
int t=0;
int n=0;
double *x;
double *y;
double x_t_1, x_t_2;
double y_t_1, y_t_2;
int c;
int k;
int i,j;

k = scanf("%d", &t);

if(t<1 || t>10){
return 0;
}

for(c=0;c<t;c++)
{
k = scanf("%d", &n);

if(n<1 || n>100){
return 0;
}
x = (double *)malloc(sizeof(double)*n);
y = (double *)malloc(sizeof(double)*n);
memset(x, 0, sizeof(double)*n);
memset(y, 0, sizeof(double)*n);

if(x == NULL || y == NULL){
return 0;
}
j=0;
while(j<n)
{
scanf("%lf %lf", &x[j], &y[j]);
if( -10000.0 <x[j] <10000.0 && -10000.0 <y[j] <10000)
{
j++;
}else{
return 0;
}
}
//计算
for(i=0;i<n;i++)
{

for(j=i+1;j<n;j++)
{

for(k=j+1;k<n;k++)
{

x_t_2 =x[i]*y[j]+y[i]*x[k]+x[j]*y[k];

x_t_2 = x_t_2 - x[k]*y[j] - x[j]*y[i]-x[i]*y[k];

if(x_t_2 > -0.0000001 && x_t_2 < 0.0000001)
//if(fabs(x_t_2 ) <= 1e-15)
{
printf("Yes\n");
goto next_test;
}
//注，多余的代码删除了，可能会影响系统测试结果

}
}
}
printf("No\n");

next_test:
free(x);
free(y);
}
return 0;
}``````

``````/*
USER_ID: test#liuzhuchen2016
PROBLEM: 85
SUBMISSION_TIME: 2016-02-27 11:01:13
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
int t=0;
int n=0;
double *x;
double *y;
double x_t_1, x_t_2;
double y_t_1, y_t_2;
int c;
int k;
int i,j;

k = scanf("%d", &t);

if(t<1 || t>10){
return 0;
}

for(c=0;c<t;c++)
{
k = scanf("%d", &n);

if(n<1 || n>100){
return 0;
}
x = (double *)malloc(sizeof(double)*n);
y = (double *)malloc(sizeof(double)*n);
memset(x, 0, sizeof(double)*n);
memset(y, 0, sizeof(double)*n);

if(x == NULL || y == NULL){
return 0;
}
j=0;
while(j<n)
{
scanf("%f %f", &x[j], &y[j]);
if( -10000.0 <x[j] <10000.0 && -10000.0 <y[j] <10000)
{
j++;
}else{
return 0;
}
}
//计算
for(i=0;i<n;i++)
{

for(j=i+1;j<n;j++)
{
//x_t_1 = x[i]-x[j];
//y_t_1 = y[i]-y[j];
for(k=j+1;k<n;k++)
{

x_t_2 =x[i]*y[j]+y[i]*x[k]+x[j]*y[k];
//printf("%d\n", x_t_2);
x_t_2 = x_t_2 - x[k]*y[j] - x[j]*y[i]-x[i]*y[k];
//printf("%d\n", x_t_2);
if(x_t_2 > -0.00000001 && x_t_2 < 0.00000001)
{
printf("Yes\n");
goto next_test;
}
//x_t_2 = x[i]-x[k];
//y_t_2 = y[i]-y[k];
/* if(x_t_1 == 0.0 && x_t_2 == 0.0) { if(y_t_1 == 00.0 && y_t_2 == 0.0) { printf("Yes\n"); goto next_test; }else if(y_t_1 != 0.0 && y_t_2 != 0.0){ printf("Yes\n"); goto next_test; } }else if(x_t_1 != 0.0 && x_t_2 != 0.0){ if(y_t_1 == 0.0 && y_t_2 == 0.0) { printf("Yes\n"); goto next_test; }else if(y_t_1 != 0.0 && y_t_2 != 0.0){ if( (x_t_1/x_t_2)==(y_t_1/y_t_2))
{
printf("Yes\n");
goto next_test;
}
}
}else if(x_t_1 == 0.0 && x_t_2 != 0.0){
if(y_t_1 == 0.0 && y_t_2 != 0.0)
{
printf("Yes\n");
goto next_test;
}
}else if(x_t_1 != 0.0 && x_t_2 == 0.0){
if(y_t_1 != 0.0 && y_t_2 == 0.0)
{
printf("Yes\n");
goto next_test;
}
}
*/

}
}
}
printf("No\n");

next_test:
free(x);
free(y);
}
return 0;
}``````

## 关于证明三点共线的方法

B

### Brickie_liu

/** * 功能：在二维平面上，有一些点，请找出经过点数最多的那条线。[java] view plain copy /** 思路：在任意两点之间画一条无线长的直线，用散列表追踪那条直线出现的次数最多。时间复杂度...

2016/11/19
52
0
ML4T笔记 | 01-08 Optimizers: Building a parameterized model

01 - What is an optimizer What is an optimizer?: An optimizer is an algorithm that can: find minimum values for functions. find the parameters for parameterized models from data......

01/19
0
0
Pentaho6.1 CCC/CDE tool 的Extension points属性详解

Pentaho CCC/CDE tool Extension points. Pentaho CDE tool, Extension points are very useful feature. You can treat this extension points as a advance setting or property of CCC Ba......

2016/10/24
200
0
Hdu 4496 D-City

Problem Description Luxer is a really bad guy. He destroys everything he met. One day Luxer went to D-city. D-city has N D-points and M D-lines. Each D-line connects exactly two......

zoom1109
06/14
0
0

Computer Graphics Basics - Ⅰ 1. Vector Vector has length and direction Representation Usually drawn as segment with arrow-head Vector Operations Scalar Multiplicaiton Negative......

03/06
0
0

ls_cherish

4
0
redis 学习2

2
0
Spring boot 静态资源访问

0. 两个配置 spring.mvc.static-path-patternspring.resources.static-locations 1. application中需要先行的两个配置项 1.1 spring.mvc.static-path-pattern 这个配置项是告诉springboo......

moon888

4
0
hash slot（虚拟桶）

4
0
Kafka 原理和实战

vivo互联网技术

24
0