列表

详情


NC16523. 面积(area)

描述

    定义“最大生成图”:在M*N的点阵中,连接一些点形成一条经过所有点恰好一次的回路,且连成的多边形各边互不交叉。这样形成的封闭图形叫做这个点阵的“最大生成图”,用表示。(PS:这个名字是出题人胡诌的,如有雷同纯属巧合,出题人不负法律责任)

    显然,任意一个点阵都有“最大生成图”,并且有的点阵的“最大生成图”不止一个。
    如图为3*3的矩阵的一个最大生成图:

    给你一个M*N的点阵和一个三角形,问你是否可以通过若干次裁剪、拼接操作,使其某一个“最大生成图”成为该三角形?如果可以,请输出“Yes”(不含引号),否则请输出“No”。

    在本题中,M*N的点阵内,相邻两点间的距离为1(上下相邻和左右相邻),为了简便,给定三角形的两个顶点,第三个顶点是原点。

    由于Apojacsleam的计算几何往往被精度卡飞,所以他痛恨精度错误,于是给定的数字都是整数。

输入描述

输入数据有多组:

每组输入数据两行,第一行两个正整数M,N,第二行四个整数x1,y1,x2,y2,描述一个三角形数据不保证能够形成三角形。

输出描述

对于每组输入数据,输出一行描述答案:“Yes”或“No”

示例1

输入:

2 2
2 0 2 1

输出:

Yes

说明:

样例解释:

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 89ms, 内存消耗: 740K, 提交时间: 2019-10-26 14:14:24

#include<bits/stdc++.h>
using namespace std;

int main()
{
    long long M,N,x1,x2,y1,y2;
    while(~scanf("%lld%lld%lld%lld%lld%lld",&M,&N,&x1,&y1,&x2,&y2))
    {
    	(abs(x1*y2-x2*y1)+2)==N*M?printf("Yes\n"):printf("No\n");
	}
	return 0;
}

上一题