ZZULIOJ周赛 问题 E: 维克托

E: 维克托

问题描述

问题 E: 维克托
时间: 1 Sec  内存: 128 MB

题目描述
有n个向量，你可以将它们首尾相连，之后你可以在任意一个地方做一条垂直于x轴的直线，求所构成的图形与x轴围成的面积的最大是多少
注意，所围成的图形必须是封闭图形
示例图如下(图中不一定是最优解)

输入
第一行输入一个正整数n(n<=1e3)
接下来n行，每行输入两个正整数x(0<x<=1e3)，y(0<y<=1e3)，代表一个向量
输出
输出与x轴围成的面积，保留一位小数
样例输入 Copy
3
7 2
1 8
1 2
样例输出 Copy
90.0

代码

/*
    Dreams never shine!
    It's you that shine while chasing your dreams :)
    JAYO!!
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
};

bool cmp(Point p1, Point p2) {
    return (p1.y / 1.0 / p1.x) > (p2.y / 1.0 / p2.x);
}

int main() {
    vector<Point> pvec;
    int n; cin >> n;
    int t1, t2;
    double area = 0;
    for(int i = 0; i < n; i++) {
        cin >> t1 >> t2;
        pvec.push_back(Point(t1, t2));
    }
    sort(pvec.begin(), pvec.end(), cmp);
    int yy = pvec[0].y, xx = pvec[0].x;
    area = xx * yy * 0.5;
    for(int i = 1; i < pvec.size(); i++) {
        area += (yy + yy + pvec[i].y) * pvec[i].x * 0.5;
        yy += pvec[i].y;
    }
    cout << fixed << setprecision(1) << area << endl;
 	return 0;
}

总结

数学yyds！！！