hdu多校第五场1004 （hdu6627） equation 1 计算几何

题意：

给你一个C，再给你n组a,b，让你求x取什么值的时候，$ \sum_{i=1}^n |a_i*x+b_i| =C $，要求求出解的个数，并用最简分数从小到大表示，如果有无穷多解，输出-1.

题解：

其实这些方程就是在平面上的一组曲线，都是V形的，最低点都在x轴上，求出所有的零点，以这个零点从左到右排序。

容易看出，这些函数之和也是一条曲线y=f(i)，这条曲线最多有n个转折点，就是刚才那些零点，那么就在这n个转折点分出的n+1个区间内，和这n个点上，用比例公式找和y=C的交点即可。无穷多解的情况是存在一条与y=C重合的线段。

首先预处理出f(i)上所有转折点的值，注意n的范围是1e5，因此不可能让你$O(n^2)$求每一点的值，其实，只需维护a与b的前缀和和后缀和，要求某点$x_k$时，将零点在此点左边的函数取正，零点在此点右边的的函数取反。

$(\sum_{i=1}^{k-1}a_i) *x_k+\sum_{i=1}^{k-1}b_i-(\sum_{i=k+1}^{n}a_i) *x_k-\sum_{i=k+1}^{n}b_i$

注意判断零点重合情况。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<string>

#include<stack>

#include<algorithm>

using namespace std;

typedef long long LL;

typedef long long ll;

const int M = 1e5 + ;

const double eps = 1e-;

const LL mod = ;

const LL lINF = 0x3f3f3f3f3f3f3f3f;

struct node {

    int a, b;

}tr[M];

int t;

int n, c;

int fenzi[M], fenmu[M];

int ans;

int gcd(int a, int b)

{

    if (!b)

        return a;

    else

        return gcd(b, a % b);

}

double lst;

bool cmp(node x, node y)

{

    return x.a * y.b - x.b * y.a < ;

}

bool cmp2(node x, node y)

{

    return (double)x.b / -x.a < (double)y.b / -y.a;

}

bool cmp1(node x, node y)

{

    return (double)x.b / -x.a <= (double)y.b / -y.a;

}

int suma[M], sumb[M];

int flag;

double nw;

double nx;

int main()

{

    scanf("%d", &t);

    while (t--)

    {

        scanf("%d%d", &n, &c);

        for (int i = ; i <= n; i++)

        {

            scanf("%d%d", &tr[i].a, &tr[i].b);

        }

        sort(tr + , tr + n + , cmp);

        suma[] = sumb[] = ;

        for (int i = ; i <= n; i++)

        {

            suma[i] = suma[i - ] + tr[i].a;

            sumb[i] = sumb[i - ] + tr[i].b;

        }

        flag = ans = ;

        lst = -10000.0;

        for (int i = ; i <= n; i++)

        {

            int tmpa = -suma[n];

            int tmpb = -sumb[n];

            tmpa +=  * suma[i];

            tmpb +=  * sumb[i];

            nw = (double)sumb[i] / suma[i];

            nx = (double)sumb[i + ] / suma[i + ];

            if (fabs(nw - nx) < eps)

                continue;

            if (!tmpa && tmpb == c)

            {

                flag = ;

                break;

            }

            if (!i)

            {

                node tmpc;

                tmpc.a = tmpa, tmpc.b = tmpb - c;

                if (cmp1(tmpc, tr[]))

                {

                    fenzi[ans] = -tmpc.b;

                    fenmu[ans] = tmpa;

                    int d = gcd(fenzi[ans], fenmu[ans]);

                    fenzi[ans] /= d;

                    fenmu[ans] /= d;

                    if (fenmu[ans] < )

                    {

                        fenzi[ans] = -fenzi[ans], fenmu[ans] = -fenmu[ans];

                    }

                    ans++;

                }

            }

            else if (i == n)

            {

                node tmpc;

                tmpc.a = tmpa, tmpc.b = tmpb - c;

                if (cmp2(tr[n], tmpc))

                {

                    fenzi[ans] = -tmpc.b;

                    fenmu[ans] = tmpa;

                    int d = gcd(fenzi[ans], fenmu[ans]);

                    fenzi[ans] /= d;

                    fenmu[ans] /= d;

                    if (fenmu[ans] < )

                    {

                        fenzi[ans] = -fenzi[ans], fenmu[ans] = -fenmu[ans];

                    }

                    ans++;

                }

            }

            else

            {

                node tmpc;

                tmpc.a = tmpa, tmpc.b = tmpb - c;

                if (cmp2(tr[i], tmpc) && cmp1(tmpc, tr[i + ]))

                {

                    fenzi[ans] = -tmpc.b;

                    fenmu[ans] = tmpa;

                    int d = gcd(fenzi[ans], fenmu[ans]);

                    fenzi[ans] /= d;

                    fenmu[ans] /= d;

                    if (fenmu[ans] < )

                    {

                        fenzi[ans] = -fenzi[ans], fenmu[ans] = -fenmu[ans];

                    }

                    ans++;

                }

            }

            lst = (double)(tmpb - c) / tmpa;

        }

        if (flag)

        {

            printf("-1\n");

        }

        else

        {

            printf("%d", ans);

            for (int i = ; i < ans; i++)

            {

                printf(" %d/%d", fenzi[i], fenmu[i]);

            }

            puts("");

        }

    }

}

巴特西

hdu多校第五场1004 （hdu6627） equation 1 计算几何

最新文章

热门文章