文档章节

85. Three Points On A Line

B
 Brickie_liu
发布于 2017/04/18 18:31
字数 997
阅读 2
收藏 0

时间限制 1000 ms 内存限制 65536 KB

题目描述

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;
}

关于证明三点共线的方法

方法一:取两点确立一条直线,计算该直线的解析式 .代入第三点坐标 看是否满足该解析式 (直线与方程).
方法二:设三点为A、B、C .利用向量证明:λAB=AC(其中λ为非零实数).
方法三:利用点差法求出AB斜率和AC斜率,相等即三点共线.
方法四:用梅涅劳斯定理.
方法五:利用几何中的公理“如果两个不重合的平面有一个公共点,那么它们有且只有一条过该点的公共直线”.可知:如果三点同属于两个相交的平面则三点共线.
方法六:运用公(定)理 “过直线外一点有且只有一条直线与已知直线平行(垂直)”.其实就是同一法.
方法七:证明其夹角为180°.
方法八:设A B C ,证明△ABC面积为0.
方法九:帕普斯定理.
方法十:利用坐标证明。即证明x1y2=x2y1.
方法十一:位似图形性质.

本文转载自:http://blog.csdn.net/liuzhuchen/article/details/50754507

B
粉丝 0
博文 20
码字总数 0
作品 0
私信 提问
在二维平面上,有一些点,请找出经过点数最多的那条线。

/** * 功能:在二维平面上,有一些点,请找出经过点数最多的那条线。[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
计算机图形学 Week 2_Basics - Ⅰ

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

鲸90830
03/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分布式协调服务zookeeper

ps.本文为《从Paxos到Zookeeper 分布式一致性原理与实践》笔记之一 ZooKeeper ZooKeeper曾是Apache Hadoop的一个子项目,是一个典型的分布式数据一致性的解决方案,分布式应用程序可以基于它...

ls_cherish
今天
4
0
redis 学习2

网站 启动 服务端 启动redis 服务端 在redis 安装目录下 src 里面 ./redis-server & 可以指定 配置文件或者端口 客户端 在 redis 的安装目录里面的 src 里面 ./redis-cli 可以指定 指定 连接...

之渊
昨天
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(虚拟桶)

在分布式集群中,如何保证相同请求落到相同的机器上,并且后面的集群机器可以尽可能的均分请求,并且当扩容或down机的情况下能对原有集群影响最小。 round robin算法:是把数据mod后直接映射...

李朝强
昨天
4
0
Kafka 原理和实战

本文首发于 vivo互联网技术 微信公众号 https://mp.weixin.qq.com/s/bV8AhqAjQp4a_iXRfobkCQ 作者简介:郑志彬,毕业于华南理工大学计算机科学与技术(双语班)。先后从事过电子商务、开放平...

vivo互联网技术
昨天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部