2022牛客多校四_G M

2022牛客多校四

一杯咖啡一道大分讨做一天
谢谢队友帮我一起debug

传送门

G - Wall Builder I

嘿嘿，大分类讨论！

prob.: 造房子，给一个大矩形和若干点，点可看做射线发射器，分割矩形，问最大矩形面积最大是多少

ideas： 转三次，每次分几类讨论，可以见注释

code：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> vl, vr, vb, vt;
ll ans;
ll n, a, b;

void turnClockwise() {
    
    vector<ll> tmpvl, tmpvr, tmpvb, tmpvt;
    for (auto x : vb) tmpvl.push_back(x);
    for (auto x : vt) tmpvr.push_back(x);
    for (auto x : vr) tmpvb.push_back(x);
    for (auto x : vl) tmpvt.push_back(x);
    vl.clear(), vr.clear(), vb.clear(), vt.clear();
    for (auto x : tmpvl) vl.push_back(a - x);
    for (auto x : tmpvr) vr.push_back(a - x);
    for (auto x : tmpvb) vb.push_back(x);
    for (auto x : tmpvt) vt.push_back(x);
    sort(vl.begin(), vl.end(), [&](ll x, ll y) {
     return x < y; });
    sort(vr.begin(), vr.end(), [&](ll x, ll y) {
     return x < y; });
    sort(vb.begin(), vb.end(), [&](ll x, ll y) {
     return x < y; });
    sort(vt.begin(), vt.end(), [&](ll x, ll y) {
     return x < y; });
    swap(a, b);
}

void solve() {
    
    // zero
    if (n == 0) {
    
        ll tmp = a * b;
        ans = max(tmp, ans);
    }
    // one
    vector<ll> bothLR;
    for (auto x : vl) bothLR.push_back(x);
    for (auto x : vr) bothLR.push_back(x);
    sort(bothLR.begin(), bothLR.end(), [&](ll x, ll y) {
     return x < y; });
    if (vb.empty()) {
    
        if(!bothLR.empty()) {
    
            ll tmp = a * bothLR[0];
            ans = max(tmp, ans);
        }
    }
    // two
    // - strip
    if (bothLR.size() >= 2) {
    
        for (ll i = 1; i < bothLR.size(); ++i) {
    
            ll tmp = (bothLR[i] - bothLR[i - 1]) * a;
            ans = max(tmp, ans);
        }
    }
    vector<ll> bothTB;
    for(auto x : vb) bothTB.push_back(x);
    for(auto x : vt) bothTB.push_back(x);
    sort(bothTB.begin(), bothTB.end(), [&](ll x, ll y){
    return x< y;});
    if (bothTB.size() >= 2) {
    
        for (ll i = 1; i < bothTB.size(); ++i) {
    
            ll tmp = (bothTB[i] - bothTB[i - 1]) * b;
            ans = max(tmp, ans);
        }
    }
    // - left bottom
    // - - left bottom
    if (!vb.empty() && !vl.empty()) {
    
        ll tmp = vb[0] * vl[0];
        ans = max(tmp, ans);
    }
    // - - top left 1
    if (vb.empty() && !vl.empty() && !vt.empty()) {
    
        ll tmp = vl[0] * vt[vt.size() - 1];
        ans = max(ans, tmp);
    }
    // - - right bottom
    if(!vb.empty() && vl.empty() && !vr.empty()) {
    
        ll tmp = vr[vr.size() - 1] * vb[0];
        ans = max(tmp, ans);
    }
    // three
    // - 2 from bottom + bothLR highest
    if (!bothLR.empty()) {
    
        ll h = bothLR[bothLR.size() - 1];
        if (vb.size() >= 2) {
    
            for (ll i = 1; i < vb.size(); ++i) {
    
                ll tmp = (vb[i] - vb[i - 1]) * h;
                ans = max(tmp, ans);
            }
        }
    }
    // - top_ rightmost + bottom_ rightmost + vl highest
    if (!vl.empty() && !vb.empty() && !vt.empty()) {
    
        ll h = vl[vl.size() - 1];
        ll w1 = vb[vb.size() - 1];
        ll w2 = vt[vt.size() - 1];
        ll tmp = (w2 - w1) * h;
        ans = max(tmp, ans);
    }
    // - top_ leftmost + bottom_ leftmost + vr highest
    if (!vr.empty() && !vb.empty() && !vt.empty()) {
    
        ll h = vr[vr.size() - 1];
        ll w1 = vb[0];
        ll w2 = vt[0];
        ll tmp = (w1 - w2) * h;
        ans = max(tmp, ans);
    }
}

signed main() {
    
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    ll _;
    cin >> _;
    while (_--) {
    
        vl.clear(), vr.clear(), vb.clear(), vt.clear();
        ans = 0;
        cin >> n >> a >> b;
        for (ll i = 1; i <= n; ++i) {
    
            ll x, y;
            cin >> x >> y;
            if (x == 0) vl.push_back(y);
            else if (x == a) vr.push_back(y);
            else if (y == 0) vb.push_back(x);
            else if (y == b) vt.push_back(x);
        }
        sort(vl.begin(), vl.end(), [&](ll x, ll y) {
     return x < y; });
        sort(vr.begin(), vr.end(), [&](ll x, ll y) {
     return x < y; });
        sort(vb.begin(), vb.end(), [&](ll x, ll y) {
     return x < y; });
        sort(vt.begin(), vt.end(), [&](ll x, ll y) {
     return x < y; });

        solve();
        turnClockwise();
        solve();
        turnClockwise();
        solve();
        turnClockwise();
        solve();

        cout << ans << endl;
    }
    return 0;
}

一张草稿纸：（不保正确）

M - Monotone Chain

prob. : 二维平面，给一堆点$A_1\dots A_n$, 要求两个向量$\vec{a}$, $\vec{b}$ ，st. $\forall 1\le i<j\le n,((\overrightarrow{O{A}_i}-\vec{a})\cdot \vec{b}\le (\overrightarrow{O{A}_j}-\vec{a})\cdot \vec{b})$

ideas:$\vec{a}$ 是可以直接消掉的，然后移项
$$\begin{array}{rl}((\overrightarrow{O{A}_i}-\vec{a})\cdot \vec{b}& \le (\overrightarrow{O{A}_j}-\vec{a})\cdot \vec{b})\\ \overrightarrow{O{A}_i}\cdot \vec{b}& \le \overrightarrow{O{A}_j}\cdot \vec{b}\\ (\overrightarrow{O{A}_i}-\overrightarrow{O{A}_j})\cdot \vec{b}& \le 0\\ \overrightarrow{A_j{A}_i}\cdot \vec{b}& \le 0\\ \overrightarrow{A_i{A}_j}\cdot \vec{b}& \ge 0\end{array}$$

相当于是每个线段在直线上的投影都是正的）

直接做就行，对于每段线段都可以求出一个角度范围，然后求交集

实际实现的时候可以对于每个位置记录一个边界角度，如果n条线段算出来的边界角度范围小于180（pi），则可行，可行解为边界角度+90（

判可行的时候将角度排序然后看有没有相邻角度大于180（pi），若有则直接可行（剩余的会落在小于180的区间内则达成上述条件

code:

（队友写的我直接cv过来//

///
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f,N=2e5+5;
const double PI=acos(-1),eps=1e-12;

struct P{
    
    ll x,y;
    double ang;
}p[N];

int main(){
    
    #ifdef ONLINE_JUDGE
        //std::ios::sync_with_stdio(false);
    #else
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
    
        scanf("%lld%lld",&p[i].x,&p[i].y);
        if(i&&p[i].x==p[i-1].x&&p[i].y==p[i-1].y){
    
            i--,n--;
        }
    }
    assert(n!=2);
    if(n==1){
    
        printf("YES\n1 1 1 1");
        return 0;
    }
    n--;
    for(int i=0;i<n;i++){
    
        p[i]={
    p[i+1].x-p[i].x,p[i+1].y-p[i].y,0};
        p[i].ang=atan2(p[i].y,p[i].x);
    }
    sort(p,p+n,[](P a,P b){
    
        return a.ang<b.ang;
    });
    if(n==1){
    
        printf("YES\n1 1 %lld %lld\n",p[0].y,-p[0].x);
        return 0;
    }
    int pos=-1;
    for(int i=0;i<n;i++){
    
        double o=p[(i+1)%n].ang-p[i].ang;
        //cout<<o<<endl;
        if(o>PI-eps||(o<-eps&&o>-PI-eps)){
    
            pos=i;
        }
    }
    if(pos!=-1)printf("YES\n1 1 %lld %lld\n",p[pos].y,-p[pos].x);
    else printf("NO\n");
    return 0;
}