codeforces怎么提交，Codeforces Round #198 (Div. 2)A,B題解

Codeforces Round #198 (Div. 2)

昨天看到奮斗群的群賽,好奇的去做了一下,

大概花了3個小時Ak,我大概可以退役了吧

codeforces怎么提交，那下面來稍微總結一下

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.

Code 82？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

3

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題,題意很明晰,

codeforces div難度？求出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);
}

?

B. Maximal Area Quadrilateral

codeforces難度、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

5
0 0
0 4
4 0
4 4
2 3

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

codeforces題解，首先我們可以把一個四邊形分成兩個三角形來求

這樣那我們可以O(n^2)枚舉對角線,然后就可以求出上三角形的最大值和下三角形的最大值

我們就可以得出最大的四邊形的面積,

求三角形面積可以用叉積,這樣,就可以得到了O(n^3)的了

code for、***如果不會叉積的,極力推薦去學習一下計算幾何初步

#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\n",s/2.0);
}