Codeforces Round #198 (Div. 2)A,B题解

昨天看到奋斗群的群赛,好奇的去做了一下,

大概花了3个小时Ak,我大概可以退役了吧

那下面来稍微总结一下

A. The Wall

Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on.

Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.

After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question.

input

2 3 6 18

output

Note

Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18.

一句话题意:给你a,b,n,m,求在[n,m](闭区间)内有多少个数可以同时整除a和b

很显然非常清真的一道A题,题意很明晰,

求出a,b的最小公倍数,然后求出n以内和m以内各有几个,

最后相减,注意因为是闭区间,所以要特判n是否符合

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,n,m;
    scanf("%d%d%d%d",&a,&b,&n,&m);
    int lcs=a/__gcd(a,b)*b,ans1=n/lcs,ans2=m/lcs;
    if (n%lcs==0) ans1--;
    printf("%d",ans2-ans1);
}

View Code

B. Maximal Area Quadrilateral

Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.

input

output

16.000000

Note

In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.

一句话题意:给你n个点,让你选出四个点,使得这四个点组成的四边形面积最大

感觉这道题其实有D题的难度,可参见考试时A掉人数:A>D>C>B>E

首先我们可以把一个四边形分成两个三角形来求

这样那我们可以O(n^2)枚举对角线,然后就可以求出上三角形的最大值和下三角形的最大值

我们就可以得出最大的四边形的面积,

求三角形面积可以用叉积,这样,就可以得到了O(n^3)的了

***如果不会叉积的,极力推荐去学习一下计算几何初步

#include <cstdio>
#include <complex>
#include <algorithm>
using namespace std;
typedef complex<int> xint;
const int inf=1000010000;
xint point[330];
int crs(xint a,xint b){
    return (a.real()*b.imag()-a.imag()*b.real());
}

int main(){
     int n,s=0; scanf("%d",&n);
      for (int i=0,x,y;i<n&&2==scanf("%d %d",&x,&y);++i) 
          point[i]=xint(x,y);
    for (int i=0;i<n;++i)
        for (int j=i+1;j<n;++j){
            int a=inf,b=-inf;
            for (int k=0;k<n;++k){
                  int c=crs(point[k]-point[i],point[j]-point[i]);
                  if(c<0) a=min(a,c); else if(c>0) b=max(b,c);
                  if(a<0&&b>0) s=max(s,b-a);
                }
          }
      printf("%.8lf
",s/2.0);
}

View Code