欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018年北京信息科技大学第十届程序设计竞赛暨ACM选拔赛 C 颜料的混合 (计算几何)

程序员文章站 2022-03-30 09:03:32
...

题意:感觉题目描述不清楚。。。也许是自己菜把。。题意是给你是3种颜料,他们都有一个红度和一个绿度,红度和绿度相同就表明他们的颜色相同,现在他现在给你一个新的颜色,问你能不能由这三个颜色组成。

思路 :我们把两个颜色抽象成一个线段的两个端点,那么显然我们这个线段上的所有颜色我们都能由这两个颜色组成,那么给你三个颜色,我们就能想到是一个三角形,也就是说新的颜色只要在三角形内,我们都能组成就ok了,如何判断一个点在不在三角形内呢,做法就是将这个点和三角形的三个顶点都连起来,看看他们组成的面积和三角形面积比较,如果相等的话,那么我们的点就在三角形内部

#include <bits/stdc++.h>

using namespace std;

struct point
{
    int x, y;
    void input() {
        scanf("%d %d", &x, &y);
    }
    point() {}
    point(int x, int y) : x(x), y(y){}
    point operator + (const point & z) const {
        return point(x+z.x, y+z.y);
    }
    point operator - (const point & z) const {
        return point(x-z.x, y-z.y);
    }
    int operator ^ (const point & z) const {
        return x * z.y - y * z.x;
    }
}p[4];
struct triangle
{
    point a,b,c;
    triangle() {}
    triangle(point a,point b,point c):a(a),b(b),c(c){}
    int area() {
        return abs( (b-a) ^ (c-a) );
    }
};

int main()
{
    while(~scanf("%d %d", &p[0].x, &p[0].y)) {
        for(int i = 1;i <= 3;i ++) p[i].input();
        triangle abc(p[1], p[2], p[3]);
        triangle abp(p[1], p[2], p[0]);
        triangle acp(p[1], p[3], p[0]);
        triangle bcp(p[2], p[3], p[0]);
//        printf("%d %d %d %d\n", abc.area(), abp.area(), acp.area(), bcp.area());
        if(abc.area() == abp.area() + acp.area() + bcp.area()) puts("Yes");
        else puts("No");
    }
    return 0;
}