Submission #554059

#	Time	Username	Problem	Language	Result	Execution time	Memory
554059		Marduk	SIR (COI15_sir)	C++14	0 / 100	1055 ms	21112 KiB

sir

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MAXN = (3e5+7), INF = (1e9+7);

struct pt{
    ll x,y;
};

int n,m;
float sol;
vector<pt> points;
vector<pt> ch;
vector<pt> pol;
pt d1 = {INF,INF}, P0 = {INF,INF};;

int distSq(pt P1, pt P2){
    return (P1.x-P2.x)*(P1.x-P2.x) + (P1.y-P2.y)*(P1.y-P2.y);
}

int ccw(pt P1, pt P2, pt P3){
    if(((P3.x-P1.x)*(P2.y-P1.y) - (P3.y-P1.y)*(P2.x-P1.x)) == 0) return 0;
    return (((P3.x-P1.x)*(P2.y-P1.y) - (P3.y-P1.y)*(P2.x-P1.x)) > 0)? -1:1;
}

bool cmp(pt P1, pt P2){
    if(ccw(P0,P1,P2) == 0) return distSq(P0,P1) < distSq(P0,P2);
    return ccw(P0,P1,P2)+1;
}

float area(pt P1, pt P2, pt P3){
    if(ccw(P1,P2,P3) == 0) return 0;
    float a = sqrt(distSq(P1,P2));
    float b = sqrt(distSq(P2,P3));
    float c = sqrt(distSq(P3,P1));
    float s = (a+b+c)/2;
    return sqrt(s*(s-a)*(s-b)*(s-c));
}

int main(){
    cin >> n;

    for(int i = 0;i<n;i++){
        int x,y; cin >> x >> y;
        if(y < d1.y || (y == d1.y && x < d1.x)) d1 = {x,y};
        pol.push_back({x,y});
    }

    cin >> m;
    for(int i = 0;i<m;i++){
        int x,y; cin >> x >> y;
        if(y < P0.y || (y == P0.y && x < P0.x)) P0 = {x,y};
        points.push_back({x,y});
    }

    sort(points.begin(), points.end(), cmp);

    ch.push_back(points[0]); ch.push_back(points[1]);
    for(int i = 2;i<points.size();i++){
        while(ccw(ch[ch.size()-2], ch[ch.size()-1], points[i])<=0) ch.pop_back();
        ch.push_back(points[i]);
    }

    P0 = d1;
    sort(pol.begin(), pol.end(), cmp);

//    cout << "paprike\n";
//    for(pt P : ch) cout << P.x << ' ' << P.y << "\n";
//    cout << "\n\n\n";

    int t = 0;
    for(int i = 0;i<n;i++){
        while(!(ccw(pol[i],ch[(t-1+ch.size())%ch.size()],ch[t]) < 0 && ccw(pol[i],ch[t],ch[(t+1)%ch.size()]) >= 0)) t = (t+1)%ch.size();
//        cout << pol[i].x << ' ' << pol[i].y << "  <->  " << ch[t].x << ' ' << ch[t].y << "\n";

        int d = (i+1)%n;
        float A = 0;
        while(ccw(pol[i],pol[d],ch[t])>0) {
//            cout << pol[d].x << ' ' << pol[d].y << " -> " << ccw(pol[i],pol[d],ch[t]) << "\n";
//            cout << "A+=" << area(pol[i],pol[d],pol[(d-1+n)%n]) << " = " << A+area(pol[i],pol[d],pol[(d-1+n)%n]) << "\n";
//            cout << "P( " << pol[i].x << ' ' << pol[i].y << " ," << pol[d].x << ' ' << pol[d].y << " ," << pol[(d-1+n)%n].x << ' ' << pol[(d-1+n)%n].y << " )\n";
            A+=area(pol[i],pol[d],pol[(d-1+n)%n]);
            d=(d+1)%n;
        }
        d = (d-1+n)%n;
//        cout << "OMG " << pol[d].x << ' ' << pol[d].y << "\n\n";
        sol = max(sol,A);
    }

    cout << sol*2;
    return 0;
}

Compilation message (stderr)

sir.cpp: In function 'int main()':
sir.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 2;i<points.size();i++){
      |                   ~^~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 39
• Subtask 3: 0 / 49