除草&& [HNOI2008]水平可见直线_Nehzilrz_百度空间
很长时间没发什么东西,贴个水题来除草。
这道题半平面交应该可以做,但是题目有特殊性所以直接拿个栈搞搞就可以了。

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define mp make_pair
#define pb push_back
#define FOR(x,y,z) for(int x(y);x<=z;++x)
#define ROF(x,y,z) for(int x(y);x>=z;--x)
#define rep(i,n) for(int i(1);i<=n;++i)
#define clr(x,y) memset(x,y,sizeof(x))
#define move(x,y) memcpy(x,y,sizeof(y))
#define two(x) (1<<(x))
#define contain(x,y) (x&two(y))
#define low(x) ((x)&-(x))
#define xx first
#define yy second
using namespace std;

typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
typedef long long ll;
typedef unsigned int uint;

const int inf=0x3f3f3f3f;
const ll infLL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI=3.141592653589793238;

template<class T> inline void chkmax(T&x,const T&y){ if (x<y) x=y; };
template<class T> inline void chkmin(T&x,const T&y){ if (x>y) x=y; };
inline double operator*(const PII&a,const PII&b){ return 1.0*(a.yy-b.yy)/(b.xx-a.xx); }

const int N=50010;

PIII a[N];
bool ans[N];
int n,s[N],top;

int main() {
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
scanf("%d",&n);
rep(i,n) {
scanf("%d%d",&a[i].xx.xx,&a[i].xx.yy);
a[i].yy=i;
}
sort(a+1,a+1+n);
top=-1;
rep(i,n) if (a[i].xx.xx!=a[i+1].xx.xx) {
while (top>0 && a[i].xx*a[s[top-1]].xx<=a[s[top]].xx*a[s[top-1]].xx) --top;
s[++top]=i;
}
FOR(i,0,top) ans[a[s[i]].yy]=true;
int i;
for (i=1;i<=n;++i) if (ans[i]){ printf("%d",i); break; }
for (++i;i<=n;++i) if (ans[i]) printf(" %d",i);
printf("\n");
}


郑重声明:资讯 【除草&& [HNOI2008]水平可见直线_Nehzilrz_百度空间】由 发布,版权归原作者及其所在单位,其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实,请读者仅作参考,并请自行核实相关内容。若本文有侵犯到您的版权, 请你提供相关证明及申请并与我们联系(qiyeku # qq.com)或【在线投诉】,我们审核后将会尽快处理。
—— 相关资讯 ——