0%

Distance

For given two segments s1 and s2, print the distance between them.

s1 is formed by end points p0 and p1, and s2 is formed by end points p2 and p3.

Read more »

Cross Point

For given two segments s1 and s2, print the coordinate of the cross point of them.

s1 is formed by end points p0 and p1, and s2 is formed by end points p2 and p3.

Read more »

Intersection

For given two segments s1 and s2, print “1” if they are intersect, “0” otherwise.

s1 is formed by end points p0 and p1, and s2 is formed by end points p2 and p3.

Read more »

Parallel/Orthogonal

For given two lines s1 and s2, print “2” if they are parallel, “1” if they are orthogonal, or “0” otherwise.

s1 crosses points p0 and p1, and s2 crosses points p2 and p3.

Read more »

Reflection

For given three points p1,p2,p, find the reflection point x of p onto p1p2.

Input

1
2
3
4
5
6
xp1 yp1 xp2 yp2
q
xp0 yp0
xp1 yp1
...
xpq−1 ypq−1

In the first line, integer coordinates of p1 and p2 are given. Then, q queries are given for integer coordinates of p.

Read more »

Projection

For given three points p1,p2,p, find the projection point x of p onto p1p2.

Input

1
2
3
4
5
6
xp1 yp1 xp2 yp2
q
xp0 yp0
xp1 yp1
...
xpq−1 ypq−1

In the first line, integer coordinates of p1 and p2 are given. Then, q queries are given for integer coordinates of p.

Read more »

不解释,不难。

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
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1e3;
struct people{
int B,J;
people(){}
people(int B,int J):B(B),J(J){}
bool operator < (const people& x)const{
return J>x.J;
}
}p[maxn];
int main(){
int n,b,j,cnt=0;
while(scanf("%d",&n),n){
for(int i=0;i<n;i++){
scanf("%d%d",&b,&j);
p[i]=people(b,j);
}
sort(p,p+n);
long long ans=0,cur=0;
for(int i=0;i<n;i++){
cur+=p[i].B;
ans=max(ans,p[i].J+cur);
}
printf("Case %d: %lld\n",++cnt,ans);
}

return 0;
}

就是贪心思想一怼。

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
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=2e4+10;
int a[maxn],b[maxn],n,m;
int main(){
while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<m;i++) scanf("%d",&b[i]);
sort(a,a+n);
sort(b,b+m);
int idx_a=0,idx_b=0;
long long ans=0;
while(idx_a<n&&idx_b<m){
if(a[idx_a]<=b[idx_b]){
ans+=b[idx_b];
idx_a++;
idx_b++;
}else idx_b++;
}
if(idx_a==n) printf("%lld\n",ans);
else printf("Loowater is doomed!\n");
}
return 0;
}

题目链接

思路

​ 本题的关键就是求第i个点的左边和右边有多少个小于i点的等级的点,分别用min_l[]和min_r[]来存储。
等级范围是$1\le a_i \le 10^5$,所以我们在对a[]数组正向遍历时直接用BIT[]数组存储某个等级的是否出现过,出现过的标记为1,否则为0,这样这个题就变成了一个区间求和的问题。
既然是区间求和问题,那么用二叉索引树(树状数组,BIT)和线段树都可以解决。

Read more »