Peienwu's Blog

Hello world

0%

牛牛牧場問題

發表於 分類於 ， Valine：
文章字數： 3.2k 所需閱讀時間 ≈ 3 分鐘

題序

從前從前有一個人名叫thanksone，他與他的兩個哥哥thankstwo以及thanksthree以及他的弟弟thankszero一起開了一家「牛牛牧場」，用來養牛以及一些奇怪的東西。

有一天，他發現他的牛牛少了很多隻，不知道是跑去了哪裡，他很難過，因此他想要建造一個圍籬，讓所有牛牛都跑不出去。於是他拜託他的兩個哥哥thankstwo以及thanksthree去市集買了$n$個用來架設圍籬的木樁，並要求他們把這些木樁架設在他指定的位置。

接著，他拜託他的弟弟thankszero也去買了條超長的圍籬，並要求thankszero利用這條超長圍籬將$n$個木樁都圍起來，才能讓牛牛有盡量大的活動空間。thankszero的數學比起他的哥哥thanksone還要糟，因此他需要拜託你幫忙計算一下當他圍好圍籬之後，有多少個木樁會剛好落在這條圍籬上。除此之外，他還希望你能給他所有在圍籬上的木樁的位置，讓他知道固定圍籬的木樁的位置。

最後，thanksone看到了你驚人的計算能力，於是他要求你計算出圍籬所圍出來的面積有多大，讓他能知道他的牛牛有多少的活動空間。

INPUT

第一行有一個正整數$n(3≤n≤2⋅10^5)$，表示有$n$個木樁在莊園上
接下來有$n$行，每行有兩個整數 $x$ 及 $y$（$−10^9≤x,y≤10^9$），以一個空白隔開，用以代表一個木樁在座標軸上的位置。

保證輸入的每一點都不會重複。

OUTPUT

第一行請輸出一個整數$k$：圍欄上木樁的個數（包含圍欄邊上的木樁）
接下來輸出$k$行，每一行為圍欄上木樁的座標，由$x$座標由小到大輸出，如果$x$座標相同則按照$y$座標大小輸出。
注意每一個木樁最多只能被輸出一次。
最後一行輸出圍欄所圍出的面積大小，資料四捨五入取到整數位。

SUBTASK

40分：$n ≤100$

60分：沒有特別限制

範例測資1

input

1
2
3
4
5
6
7
8
7
2 2
2 0
1 1
2 4
2 3
4 2
1 3

output

1
2
3
4
5
6
7
5
1 1
1 3
2 0
2 4
4 2
7

範例測資2

input

1
2
3
4
5
4
1 2
3 2
2 2
5 2

output

1
2
3
4
5
6
4
1 2
2 2
3 2
5 2
0

從範例測資1可以發現，thanksone可以將下圖木樁$B,F,D,G,C$圍起來，能獲得最大的牛牛牧場面積：

範例測資2可以看到，thanksone圍出來的牛牛牧場面積為 $0$：

題目連結

OJDL

題解

這一題就是凸包裸題，輸出所有包含在凸包上的點（頂點跟邊都要）。

subtask 1

保證所形成的凸包面積不為0，所以做完凸包之後將邊上的點都輸出出來，之後再計算凸包面積就好。

subtask 2

做完凸包可能會有點重複的問題，所以將所有點排序之後，記得去重，好好處理就可以AC了。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define pdd pair<double,double>
#define int long long
#define ll long long
#define ld long double
#define N 100001
#define all(x) x.begin(),x.end()
#define eps 1e-9
#define x first
#define y second

using namespace std;

struct pt{
    int x,y;
    bool operator < (pt const &b){
        if(x == b.x)return y < b.y;
        return x < b.x;
    }
    bool operator > (pt const &b){
        if(x == b.x)return y > b.y;
        return x > b.x;
    }
    bool operator == (pt const &b){
        if(x-b.x == 0 && y-b.y == 0)return true;
        return false;
    }
    pt operator+(pt const &b) {return {x + b.x, y + b.y};} //向量相加
    pt operator-(pt const &b) {return {x - b.x, y - b.y};} //向量相減
    int operator^(pt const &b) {return x * b.y - y * b.x;} //向量外積cross
    int operator*(pt const &b) {return x * b.x + y * b.y;} //向量內積dot
};

struct comp{
    bool operator()(pt const &a,pt const &b)const{
        if(a.x == b.x)return a.y < b.y;
        return a.x < b.x;
    }
};

vector<pt> p,temp,pp;
vector<int>  cnt;
set<pt,comp> s;
int n,ans = 0;

bool cmp(pt a, pt b){
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}

bool check(pt a,pt b,pt o){
    pt aa = a - o;
    pt bb = b - o;
    return (aa^bb) > 0;
}

vector<pt> solve(){
    sort(all(p),cmp);
    vector<pt> h;
    for(pt i : p){
        while(h.size()>=2 && check(i,h[h.size()-1],h[h.size()-2]))
            h.pop_back();
        h.push_back(i);
    }
    int sz = h.size();
    h.pop_back();
    reverse(all(p));
    for(auto i : p){
        while(h.size()>sz && check(i,h[h.size()-1],h[h.size()-2]))
            h.pop_back();
        h.push_back(i);
    }
    return h;
}

signed main(){
    cin>>n;
    p.resize(n,{0,0});
    rep(i,0,n-1)cin>>p[i].x>>p[i].y;
    vector<pt> hull = solve();
    int area = 0,sz = hull.size();
    rep(i,0,sz-2)area += (hull[i]^hull[i+1]);
    for(auto i : hull)s.insert(i);
    cout<<s.size()<<endl;
    for(auto i : s)cout<<i.x<<" "<<i.y<<endl;
    cout<<((area%2)?(area/2)+1:(area/2))<<endl;

}