题解：P14776 [ICPC 2024 Seoul R] Triangle

henbule_ · 2025-12-15 19:58:17 · 题解

本题正确思路（数学 + 枚举优化）：

1.边上的格点数量

对于两点 P=(x_1,y_1)，Q=(x_2,y_2)，线段 PQ 上（含端点）的整数点个数为：

所以，不包含端点的内部格点数为：

如果某条边的 g=0，即 \gcd(|dx|,|dy|)=1，则该边上 没有可选的非顶点整数点 → 输出 -1。

2. 新三角形面积的最大值和最小值

设原三角形为 △ABC，我们在边 AB,BC,CA 上各取一点 P,Q,R(非顶点)，构成 △PQR。

目标：求 \operatorname{area}(PQR) 的最大值和最小值。

关键结论（来自计算几何）：

面积是关于 P,Q,R 的线性函数（实际上是双线性或仿射）。

在格点线段上，极值一定出现在端点附近，即每条边上只需考虑最靠近两个端点的格点（最多两个候选点）。

这是因为面积函数在线段上是线性的（固定另两点时，面积随第三点线性变化），所以极值在边界。

因此，每条边最多只需保留 2 个候选点（第一个和最后一个内部格点）。

这样，总枚举量最多是 2 \times 2 \times 2=8 个三角形，完全可以接受！

代码奉上：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node 
{
    ll x,y;
    Node(){}
    Node(ll x,ll y):x(x),y(y){}
    Node operator+(const Node&o)const {return Node(x+o.x,y+o.y);}
    Node operator-(const Node&o)const {return Node(x-o.x,y-o.y);}
};
ll gcd(ll a, ll b) 
{
    a=llabs(a);
    b=llabs(b);
    if(b==0)return a;
    return gcd(b,a%b);
}
vector<Node>solve(const Node& p,const Node& q) 
{
    ll dx=q.x-p.x;
    ll dy=q.y-p.y;
    ll g=gcd(dx,dy);
    if(g<=1) 
    {
        return {};
    }
    ll sx=dx/g;
    ll sy=dy/g;
    vector<Node>sum;
    sum.push_back(Node(p.x+sx,p.y+sy));
    if(g>2) 
    {
        sum.push_back(Node(p.x+(g-1)*sx, p.y+(g-1)*sy));
    }
    return sum;
}
ll solve2(const Node& a,const Node& b,const Node& c) 
{
    ll rs=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
    return llabs(rs);
}
int main() 
{
    Node A,B,C;
    cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y;
    vector<Node>ab=solve(A,B);
    vector<Node>bc=solve(B,C);
    vector<Node>ca=solve(C,A);
    if(ab.empty()||bc.empty()||ca.empty()) 
    {
        cout<<"-1"<<endl;
        return 0;
    }
    ll minn=LLONG_MAX;
    ll maxn=-1;
    for(const auto& p:ab) 
    {
        for(const auto& q:bc) 
        {
            for(const auto& r:ca) 
            {
                ll a2=solve2(p,q,r);
                if(a2==0)continue;
                minn=min(minn,a2);
                maxn=max(maxn,a2);
            }
        }
    }
    cout<<maxn<<" "<<minn<<endl;
    return 0;
}