oj.uz

Submission #932394

# Submission time Handle Problem Language Result Execution time Memory
932394 2024-02-23T09:21:31 Z tminh_hk20 SIR (COI15_sir) C++14
100 / 100
 361 ms 47156 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
const int N=6e5+5;
int n,m;
struct p{
    int x,y;
};
p a[N],b[N];
vector<p> dinh;
bool cmp(p i,p j){
    if(i.x==j.x)    return i.y<j.y;
    return i.x<j.x;
}
vector<p> baoloi;
//ben trai thi tra ve true
bool check1(p a,p b,p c){
    return (b.x-a.x) *(c.y-a.y)-(c.x-a.x)*(b.y-a.y)>=0;
}
bool check(p a,p b,p c){
    return (b.x-a.x) *(c.y-a.y)-(c.x-a.x)*(b.y-a.y)>0;
}
void convexhull(){
    sort(dinh.begin(),dinh.end(),cmp);
    baoloi.push_back(dinh[0]);
    for(int i=1;i<m;i++){
        while(baoloi.size()>=2&&check(baoloi[baoloi.size()-2],baoloi[baoloi.size()-1],dinh[i])) baoloi.pop_back();
       baoloi.push_back(dinh[i]);
    }
    for(int i=m-2;i>=0;i--){
        while(baoloi.size()>=2&&check(baoloi[baoloi.size()-2],baoloi[baoloi.size()-1],dinh[i])) baoloi.pop_back();
        baoloi.push_back(dinh[i]);
    }
    if(baoloi.size()>1) baoloi.pop_back();

}
int id=0;
int kt(p x,p y,p z){
    if(x.x==y.x&&x.y==y.y)    return 1;
    if(!check(x,y,baoloi[id])&&!check(y,z,baoloi[id])&&!check(z,x,baoloi[id]))   return 0;
    return 1;
}
int get(p a, p b, p c){
    if(a.x==b.x&&a.y==b.y)  return 0;
	return abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y));
}
p luu[N];
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>luu[i].x>>luu[i].y;
    }
    for(int i=n-1;i>=0;i--){
        a[i]=luu[n-1-i];
    }
    for (int i=1;i<=n;i++) a[n-1+i] = a[i-1];

    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>b[i].x>>b[i].y;
        dinh.push_back({b[i].x,b[i].y});
    }
    convexhull();
    int sz=baoloi.size();
//    for(p i:baoloi){
//        cout<<i.x<<" "<<i.y<<endl;
//    }
    int r=1;
    int res=0;
    int ans=-1e18;
    for(int i=0;i<sz;i++){
        if(check(a[0],baoloi[id],baoloi[i]))    id=i;
    }
    for(int i=0;i<n;i++){
        while(check(a[i],baoloi[id],baoloi[(id+1)%sz])){
            id++;
            id%=sz;
        }
        //cout<<i<<" "<<baoloi[id].x<<" "<<baoloi[id].y<<endl;
        while(kt(a[i],a[r],a[r+1])){
            //congdientich
            res+=get(a[i],a[r],a[r+1]);
            r++;
        }
        ans=max(ans,res);

        res-=get(a[i],a[i+1],a[r]);
    }
    cout<<ans;
}

//>1 4
//>2 4
//>3 0
//>4 1
//>5 3

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4552 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 2 ms 4444 KB Output is correct
5 Correct 3 ms 4700 KB Output is correct
6 Correct 4 ms 4700 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 26552 KB Output is correct
2 Correct 300 ms 33964 KB Output is correct
3 Correct 260 ms 33708 KB Output is correct
4 Correct 88 ms 15444 KB Output is correct
5 Correct 246 ms 26484 KB Output is correct
6 Correct 255 ms 47156 KB Output is correct