题目链接 2012金华区域赛
Problem A
按a/b从小到大的顺序排队进行体检即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod=***;
struct ss
{
int x,y;
double p;
};
ss a[];
int n;
inline bool cmp(ss a,ss b)
{
return a.p<b.p;
}
int main()
{
while (~scanf("%d",&n))
{
if (n==) break;
int i;
for (i=;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].p=a[i].x*1.0/a[i].y;
}
sort(a+,a+n+,cmp);
ll sum=;
for (i=;i<=n;i++)
sum=((sum+sum*a[i].y%mod)%mod+a[i].x)%mod;
printf("%lld\n",sum);
}
return ;
}
Problem B
Problem C
先把所有的坐标离散化
将起点、终点和所有矩形的点
每个点4个方向，拆成4个点
然后如果一个点的一个方向能经过一次转弯直接到另一个点
就连一条边
建完图后用SPFA求最短路即可
但本题细节较多
最难处理的是墙角的转角情况
可以先把所有墙角预处理出来
一共8种情况
其他的就离散化后坐标乘2
然后用个数组标记每个点会经过几次
如果点已经在矩形内部
就直接置为经过2次
然后在判断时 判断路线上有没有经过2次以上的点
或者恰有一个墙角点但可以转弯
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define y1 hjhk
#define y2 mhgu
const int inf=(<<)-;
struct Hash : vector<int> {
void prepare() {
sort(begin(), end());
erase(unique(begin(), end()), end());
}
int get(int x) {
return lower_bound(begin(), end(), x)-begin()+;
}
} has;
int x1,y1,x2,y2,n;
struct ss
{
int x1,y1,x2,y2;
};
ss a[];
int dis[][];
int can[][];
bool mop[][][][];
queue<pair<int,int>> q;
bool vis[][];
pair<int,int> det[];
void relax(pair<int,int> from,int x2,int y2,int ndis)
{
//cout<<from.first<<" "<<from.second<<" "<<x2<<" "<<y2<<" "<<ndis<<endl;
if (ndis<dis[x2][y2])
{
dis[x2][y2]=ndis;
//cout<<from.first<<" "<<from.second<<" "<<x2<<" "<<y2<<" "<<ndis<<endl;
if (!vis[x2][y2])
{
q.push({x2,y2});
vis[x2][y2]=true;
}
}
}
int main()
{
//freopen("4444.in","r",stdin);
//freopen("out.txt","w",stdout);
while (~scanf("%d%d%d%d",&x1,&y1,&x2,&y2))
{
if (x1==&&y1==&&x2==&&y2==) return ;
scanf("%d",&n);
int i,j;
for (i=;i<=n;i++)
{
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
if (a[i].x1>a[i].x2)
swap(a[i].x1,a[i].x2);
if (a[i].y1>a[i].y2)
swap(a[i].y1,a[i].y2);
}
has.clear();
has.push_back(x1);
has.push_back(x2);
for (i=;i<=n;i++)
{
has.push_back(a[i].x1);
has.push_back(a[i].x2);
}
has.prepare();
x1=has.get(x1)*;
x2=has.get(x2)*;
for (i=;i<=n;i++)
{
a[i].x1=has.get(a[i].x1)*;
a[i].x2=has.get(a[i].x2)*;
}
has.clear();
has.push_back(y1);
has.push_back(y2);
for (i=;i<=n;i++)
{
has.push_back(a[i].y1);
has.push_back(a[i].y2);
}
has.prepare();
y1=has.get(y1)*;
y2=has.get(y2)*;
for (i=;i<=n;i++)
{
a[i].y1=has.get(a[i].y1)*;
a[i].y2=has.get(a[i].y2)*;
}
//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
//for (i=1;i<=n;i++)
// printf("%d %d %d %d\n",a[i].x1,a[i].y1,a[i].x2,a[i].y2);
memset(mop,false,sizeof(mop));
for (i=;i<=n;i++)
for (j=;j<=n;j++)
if (i!=j)
{
if (a[i].x2==a[j].x1&&a[i].y1<=a[j].y1)
{
mop[a[j].x1][a[j].y1][][]=true;
mop[a[j].x1][a[j].y1][][]=true;
//cout<<a[j].x1<<" "<<a[j].y1<<" "<<1<<" "<<2<<endl; }
if (a[i].y2==a[j].y1&&a[i].x2<=a[j].x2)
{
mop[a[i].x2][a[i].y2][][]=true;
mop[a[i].x2][a[i].y2][][]=true;
//cout<<a[i].x2<<" "<<a[i].y2<<" "<<1<<" "<<2<<endl;
}
if (a[i].x2==a[j].x1&&a[i].y2<=a[j].y2)
{
mop[a[i].x2][a[i].y2][][]=true;
mop[a[i].x2][a[i].y2][][]=true;
//cout<<a[i].x2<<" "<<a[i].y2<<" "<<2<<" "<<1<<endl;
}
if (a[i].y2==a[j].y1&&a[i].x1<=a[j].x1)
{
mop[a[j].x1][a[j].y1][][]=true;
mop[a[j].x1][a[j].y1][][]=true;
//cout<<a[j].x1<<" "<<a[j].y1<<" "<<2<<" "<<1<<endl;
}
if (a[i].x2==a[j].x1&&a[i].y1>=a[j].y1)
{
mop[a[i].x2][a[i].y1][][]=true;
mop[a[i].x2][a[i].y1][][]=true;
//cout<<a[i].x2<<" "<<a[i].y1<<" "<<1<<" "<<0<<endl;
}
if (a[i].y2==a[j].y1&&a[i].x1>=a[j].x1)
{
mop[a[i].x1][a[i].y2][][]=true;
mop[a[i].x1][a[i].y2][][]=true;
//cout<<a[i].x1<<" "<<a[i].y2<<" "<<1<<" "<<0<<endl;
}
if (a[i].y2==a[j].y1&&a[i].x2>=a[j].x2)
{
mop[a[j].x2][a[j].y1][][]=true;
mop[a[j].x2][a[j].y1][][]=true;
//cout<<a[j].x2<<" "<<a[j].y1<<" "<<0<<" "<<1<<endl;
}
if (a[i].x2==a[j].x2&&a[i].y2>=a[j].y2)
{
mop[a[j].x1][a[j].y2][][]=true;
mop[a[j].x1][a[j].y2][][]=true;
//cout<<a[j].x1<<" "<<a[j].y2<<" "<<0<<" "<<1<<endl;
}
}
memset(can,,sizeof(can));
//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
for (i=;i<=n;i++)
{
for (int x=a[i].x1;x<=a[i].x2;x++)
for (int y=a[i].y1;y<=a[i].y2;y++)
{
can[x][y]++;
if (x!=a[i].x1&&x!=a[i].x2&&y!=a[i].y1&&y!=a[i].y2)
{
can[x][y]=;
//if (x==11&&y==60)
// cout<<a[i].x1<<" "<<a[i].x2<<" "<<a[i].y1<<" "<<a[i].y2<<endl;
}
if (can[x][y]>) can[x][y]=;
//cout<<x<<" "<<y<<" "<<can[x][y]<<endl;
}
}
for (i=;i<=n;i++)
for (j=;j<=n;j++)
if (i!=j)
{
if (a[i].x2==a[j].x1&&a[i].y1==a[j].y1) can[a[i].x2][a[i].y1]=;
if (a[i].x2==a[j].x1&&a[i].y2==a[j].y2) can[a[i].x2][a[i].y2]=;
if (a[i].y2==a[j].y1&&a[i].x1==a[j].x1) can[a[i].x1][a[i].y2]=;
if (a[i].y2==a[j].y1&&a[i].x2==a[j].x2) can[a[i].x2][a[i].y2]=;
}
int cnt=;
det[].first=x1;
det[].second=y1;
for (i=;i<=n;i++)
{
det[++cnt].first=a[i].x1;
det[cnt].second=a[i].y1;
det[++cnt].first=a[i].x1;
det[cnt].second=a[i].y2;
det[++cnt].first=a[i].x2;
det[cnt].second=a[i].y1;
det[++cnt].first=a[i].x2;
det[cnt].second=a[i].y2;
}
det[++cnt].first=x2;
det[cnt].second=y2;
for (i=;i<=cnt;i++)
dis[i][]=dis[i][]=dis[i][]=dis[i][]=inf;
dis[][]=;
dis[][]=;
dis[][]=;
dis[][]=;
memset(vis,false,sizeof(vis));
vis[][]=true;
vis[][]=true;
vis[][]=true;
vis[][]=true;
while (!q.empty()) q.pop();
q.push({,});
q.push({,});
q.push({,});
q.push({,});
while (!q.empty())
{
pair<int,int> x=q.front();
q.pop();
vis[x.first][x.second]=false;
//cout<<det[x.first].first<<" "<<det[x.first].second<<endl;
//cout<<x.second<<endl;
//cout<< dis[x.first][x.second]<<endl;
for (i=;i<=cnt;i++)
if (i!=x.first)
{
int x1=det[x.first].first;
int y1=det[x.first].second;
int x2=det[i].first;
int y2=det[i].second;
//cout<<i<<" "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
if (x.second==)
{
if (x2==x1&&y2<y1)
{
bool fg=true;
for (int y=y2;y<=y1;y++)
if (can[x1][y]==)
{
fg=false;
break;
}
if (fg)
relax(x,i,,dis[x.first][x.second]);
}
else if (x2<x1&&y2<y1)
{
int fg=;
for (int y=y2;y<=y1;y++)
if (can[x1][y]==)
{
fg++;
}
for (int x=x2;x<=x1;x++)
if (can[x][y2]==)
{
fg++;
}
if (fg==||(fg==&&can[x1][y2]==&&mop[x1][y2][][]))
relax(x,i,,dis[x.first][x.second]+);
}
else if (x2>x1&&y2<y1)
{
int fg=;
for (int y=y2;y<=y1;y++)
if (can[x1][y]==)
{
fg++;
//break;
}
for (int x=x1;x<=x2;x++)
if (can[x][y2]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x1][y2]==&&mop[x1][y2][][]))
relax(x,i,,dis[x.first][x.second]+);
}
relax(x,x.first,,dis[x.first][x.second]+);
relax(x,x.first,,dis[x.first][x.second]+);
}
else if (x.second==)
{
if (x2<x1&&y2==y1)
{
bool fg=true;
for (int x=x2;x<=x1;x++)
if (can[x][y2]==)
{
fg=false;
break;
}
if (fg)
relax(x,i,,dis[x.first][x.second]);
}
else if (x2<x1&&y2<y1)
{
int fg=;
for (int y=y2;y<=y1;y++)
if (can[x2][y]==)
{
fg++;
//break;
}
for (int x=x2;x<=x1;x++)
if (can[x][y1]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x2][y1]==&&mop[x2][y1][][]))
relax(x,i,,dis[x.first][x.second]+);
}
else if (x2<x1&&y2>y1)
{
int fg=;
for (int y=y1;y<=y2;y++)
if (can[x2][y]==)
{
fg++;
//break;
}
for (int x=x2;x<=x1;x++)
if (can[x][y1]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x2][y1]==&&mop[x2][y1][][]))
relax(x,i,,dis[x.first][x.second]+);
}
relax(x,x.first,,dis[x.first][x.second]+);
relax(x,x.first,,dis[x.first][x.second]+); }
else if (x.second==)
{
if (x2==x1&&y2>y1)
{
bool fg=true;
for (int y=y1;y<=y2;y++)
if (can[x2][y]==)
{
fg=false;
break;
}
if (fg)
relax(x,i,,dis[x.first][x.second]);
}
else if (x2<x1&&y2>y1)
{
int fg=;
for (int y=y1;y<=y2;y++)
if (can[x1][y]==)
{
fg++;
//break;
}
for (int x=x2;x<=x1;x++)
if (can[x][y2]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x1][y2]==&&mop[x1][y2][][]))
relax(x,i,,dis[x.first][x.second]+);
}
else if (x2>x1&&y2>y1)
{
int fg=;
for (int y=y1;y<=y2;y++)
if (can[x1][y]==)
{
fg++;
//break;
}
for (int x=x1;x<=x2;x++)
if (can[x][y2]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x1][y2]==&&mop[x1][y2][][]))
relax(x,i,,dis[x.first][x.second]+);
}
relax(x,x.first,,dis[x.first][x.second]+);
relax(x,x.first,,dis[x.first][x.second]+); }
else if (x.second==)
{
if (x2>x1&&y2==y1)
{
bool fg=true;
for (int x=x1;x<=x2;x++)
if (can[x][y2]==)
{
//cout<<x<<" "<<y2<<endl;
fg=false;
break;
}
//cout<<fg<<" "<<cnt<<" "<<i<<endl;
if (fg)
relax(x,i,,dis[x.first][x.second]);
}
else if (x2>x1&&y2<y1)
{
int fg=;
for (int y=y2;y<=y1;y++)
if (can[x2][y]==)
{
fg++;
//break;
}
for (int x=x1;x<=x2;x++)
if (can[x][y1]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x2][y1]==&&mop[x2][y1][][]))
relax(x,i,,dis[x.first][x.second]+);
}
else if (x2>x1&&y2>y1)
{
int fg=;
for (int y=y1;y<=y2;y++)
if (can[x2][y]==)
{
fg++;
//break;
}
for (int x=x1;x<=x2;x++)
if (can[x][y1]==)
{
fg++;
//break;
}
if (fg==||(fg==&&can[x2][y1]==&&mop[x2][y1][][]))
relax(x,i,,dis[x.first][x.second]+);
}
relax(x,x.first,,dis[x.first][x.second]+);
relax(x,x.first,,dis[x.first][x.second]+);
}
}
}
int ans=inf;
ans=min(dis[cnt][],ans);
ans=min(dis[cnt][],ans);
ans=min(dis[cnt][],ans);
ans=min(dis[cnt][],ans);
if (ans==inf) puts("-1");
else printf("%d\n",ans);
}
return ;
}
Problem D
直接把180度分成3000分然后枚举取最小值即可。
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)for (int i(a); i <= (b); ++i)
#define dec(i, a, b)for (int i(a); i >= (b); --i)const double d = 3000;
const double pi = acos(-1.0);
const double g = 9.8000000;
const int N = 2003;double v[N];
double l1, r1, l2, r2;
int n;
double h;
int ans = 0;
int now;int solve(double ap){
int ret = 0;
rep(i, 1, n){
double now;
now = sqrt(v[i] * v[i] * sin(ap) * sin(ap) + 2 * h * g);
now = (now - v[i] * sin(ap)) / g * v[i] * cos(ap);if (now >= l2 && now <= r2) return -1;
if (now >= l1 && now <= r1) ++ret;
}return ret;
}int main(){while (~scanf("%d", &n), n){
ans = 0;
scanf("%lf%lf%lf%lf%lf", &h, &l1, &r1, &l2, &r2);
rep(i, 1, n) scanf("%lf", v + i);for (double i = -0.5 * pi; i <= 0.5 * pi; i += (pi / d)){
now = solve(i);
if (~now) ans = max(ans, now);
}now = solve(-0.5 * pi);
if (~now) ans = max(ans, now);
now = solve(0);
if (~now) ans = max(ans, now);
now = solve(0.5 * pi);
if (~now) ans = max(ans, now);
printf("%d\n", ans);
}return 0;
}
Problem E
Problem F
分解了十几项发现
$f_{x} = g_{a_{1}} * g_{a_{2}} * … * g_{a_{m}}$，m为x的约数个数。
$a_{1},a_{2},…,a_{m}$分别为x的约数。
我们预处理出$g_{x}，g_{x} = f_{x} / g_{a_{1}} / g_{a_{2}} / … / g_{a_{m-1}}$
然后就可以计算答案了。
#include <bits/stdc++.h>using namespace std;#define rep(i, a, b)for (int i(a); i <= (b); ++i)
#define dec(i, a, b)for (int i(a); i >= (b); --i)const int N = 2200;vector <int> c[N];struct dxs{
int l;
int d[N];
dxs(){ memset(d, 0, sizeof d); l = 1;}
} a[N];int n;inline dxs chu(dxs a, dxs b){
dxs ret;
ret.l = a.l - b.l + 1;
memset(ret.d, 0, sizeof ret.d);
dec(i, a.l - 1, b.l - 1){
int tt = a.d[i] / b.d[b.l - 1];
if (tt != 0){
rep(j, 0, b.l - 1){
a.d[i - j] -= tt * b.d[b.l - 1 - j];
}ret.d[i - b.l + 1] = tt;
}
}
return ret;}bool cmp(int i, int j){
if (a[i].l != a[j].l) return a[i].l < a[j].l;
dec(k, a[i].l - 1, 0)
if(a[i].d[k] != a[j].d[k])
{
if(abs(a[i].d[k]) == abs(a[j].d[k]))
return a[i].d[k] < 0;
else return abs(a[i].d[k]) < abs(a[j].d[k]);
}
return false;
}void print(dxs a){
putchar('(');
dec(i, a.l - 1, 0) if (a.d[i] != 0){
if (i == 0){
if (a.d[i] > 0) putchar('+');
printf("%d", a.d[i]);
}
else{
if (a.d[i] > 0 && i != a.l - 1) putchar('+');
if (a.d[i] == -1) putchar('-');
if (abs(a.d[i]) != 1) printf("%d", a.d[i]);
if (i > 1) printf("x^%d", i);
else putchar('x');
}
}
putchar(')');
}int main(){rep(i, 2, 1100){
rep(j, 1, i) if (i % j == 0) c[i].push_back(j);
}a[1].l = 2; a[1].d[0] = -1, a[1].d[1] = 1;
rep(i, 2, 1100){
a[i].d[0] = -1; a[i].d[i] = 1; a[i].l = i + 1; a[i] = chu(a[i], a[1]);
rep(j, 2, i - 1) if (i % j == 0) a[i] = chu(a[i], a[j]);
}rep(i, 2, 1100) sort(c[i].begin(), c[i].end(), cmp);while (~scanf("%d", &n), n){
if (n == 1){
puts("x-1");
continue;
}
for (auto u : c[n]) print(a[u]);
putchar(10);
}return 0;
}
Problem G
Problem H
先求出三维的凸包
然后枚举每个面作为底面
求出旋转后所有点的坐标
最后求出底面二维凸包的面积即可
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-7
using namespace std;
const double inf=0x3f3f3f3f;
const int MAXV=;
const double EPS = 1e-;
const double pi=acos(-1.0);
//三维点
struct pt {
double x, y, z;
pt() {}
pt(double _x, double _y, double _z): x(_x), y(_y), z(_z) {}
pt operator - (const pt p1) {
return pt(x - p1.x, y - p1.y, z - p1.z);
}
pt operator + (const pt p1) {
return pt(x + p1.x, y + p1.y, z + p1.z);
}
pt operator *(const pt p){
return pt(y*p.z-z*p.y,z*p.x-x*p.z, x*p.y-y*p.x);
}
pt operator *(double d)
{
return pt(x*d,y*d,z*d);
} pt operator / (double d)
{
return pt(x/d,y/d,z/d);
}
double operator ^ (pt p) {
return x*p.x+y*p.y+z*p.z; //点乘
}
double len(){
return sqrt(x*x+y*y+z*z);
}
};
struct pp{
double x,y;
pp(){}
pp(double x,double y):x(x),y(y){}
};
struct _3DCH {
struct fac {
int a, b, c; //表示凸包一个面上三个点的编号
bool ok; //表示该面是否属于最终凸包中的面
}; int n; //初始点数
pt P[MAXV]; //初始点 int cnt; //凸包表面的三角形数
fac F[MAXV*]; //凸包表面的三角形 int to[MAXV][MAXV]; pt Cross3(pt a,pt p){
return pt(a.y*p.z-a.z*p.y, a.z*p.x-a.x*p.z, a.x*p.y-a.y*p.x); //叉乘
}
double vlen(pt a) {
return sqrt(a.x*a.x+a.y*a.y+a.z*a.z); //向量长度
}
double area(pt a, pt b, pt c) {
return vlen(Cross3((b-a),(c-a))); //三角形面积*2
}
double volume(pt a, pt b, pt c, pt d) {
return Cross3((b-a),(c-a))^(d-a); //四面体有向体积*6
}
//三维点积
double Dot3( pt u, pt v )
{
return u.x * v.x + u.y * v.y + u.z * v.z;
} //平面的法向量
pt pvec(pt a,pt b,pt c)
{
return (Cross3((a-b),(b-c)));
}
//点到面的距离
double Dis(pt a,pt b,pt c,pt d)
{
return fabs(pvec(a,b,c)^(d-a))/vlen(pvec(a,b,c));
}
//正：点在面同向
double ptof(pt &p, fac &f) {
pt m = P[f.b]-P[f.a], n = P[f.c]-P[f.a], t = p-P[f.a];
return Cross3(m , n) ^ t;
} void deal(int p, int a, int b) {
int f = to[a][b];
fac add;
if (F[f].ok) {
if (ptof(P[p], F[f]) > eps)
dfs(p, f);
else {
add.a = b, add.b = a, add.c = p, add.ok = ;
to[p][b] = to[a][p] = to[b][a] = cnt;
F[cnt++] = add;
}
}
} void dfs(int p, int cur) {
F[cur].ok = ;
deal(p, F[cur].b, F[cur].a);
deal(p, F[cur].c, F[cur].b);
deal(p, F[cur].a, F[cur].c);
} bool same(int s, int t) {
pt &a = P[F[s].a], &b = P[F[s].b], &c = P[F[s].c];
return fabs(volume(a, b, c, P[F[t].a])) < eps && fabs(volume(a, b, c, P[F[t].b])) < eps && fabs(volume(a, b, c, P[F[t].c])) < eps;
} //构建三维凸包
void construct() {
cnt = ;
if (n < )
return; /*********此段是为了保证前四个点不公面，若已保证，可去掉********/
bool sb = ;
//使前两点不公点
for (int i = ; i < n; i++) {
if (vlen(P[] - P[i]) > eps) {
swap(P[], P[i]);
sb = ;
break;
}
}
if (sb)return; sb = ;
//使前三点不公线
for (int i = ; i < n; i++) {
if (vlen(Cross3((P[] - P[]) , (P[] - P[i]))) > eps) {
swap(P[], P[i]);
sb = ;
break;
}
}
if (sb)return; sb = ;
//使前四点不共面
for (int i = ; i < n; i++) {
if (fabs(Cross3((P[] - P[]) , (P[] - P[])) ^ (P[] - P[i])) > eps) {
swap(P[], P[i]);
sb = ;
break;
}
}
if (sb)return;
/*********此段是为了保证前四个点不公面********/ fac add;
for (int i = ; i < ; i++) {
add.a = (i+)%, add.b = (i+)%, add.c = (i+)%, add.ok = ;
if (ptof(P[i], add) > )
swap(add.b, add.c);
to[add.a][add.b] = to[add.b][add.c] = to[add.c][add.a] = cnt;
F[cnt++] = add;
} for (int i = ; i < n; i++) {
for (int j = ; j < cnt; j++) {
if (F[j].ok && ptof(P[i], F[j]) > eps) {
dfs(i, j);
break;
}
}
}
int tmp = cnt;
cnt = ;
for (int i = ; i < tmp; i++) {
if (F[i].ok) {
F[cnt++] = F[i];
}
}
} //表面积
double area() {
double ret = 0.0;
for (int i = ; i < cnt; i++) {
ret += area(P[F[i].a], P[F[i].b], P[F[i].c]);
}
return ret / 2.0;
} //体积
double volume() {
pt O(, , );
double ret = 0.0;
for (int i = ; i < cnt; i++) {
ret += volume(O, P[F[i].a], P[F[i].b], P[F[i].c]);
}
return fabs(ret / 6.0);
} //表面三角形数
int facetCnt_tri() {
return cnt;
} //表面多边形数
int facetCnt() {
int ans = ;
for (int i = ; i < cnt; i++) {
bool nb = ;
for (int j = ; j < i; j++) {
if (same(i, j)) {
nb = ;
break;
}
}
ans += nb;
}
return ans;
}
pt centroid(){
pt ans(,,),o(,,);
double all=;
for(int i=;i<cnt;i++)
{
double vol=volume(o,P[F[i].a],P[F[i].b],P[F[i].c]);
ans=ans+(o+P[F[i].a]+P[F[i].b]+P[F[i].c])/4.0*vol;
all+=vol;
}
ans=ans/all;
return ans;
}
double res(){
pt a=centroid();
double _min=1e10;
for(int i=;i<cnt;++i){
double now=Dis(P[F[i].a],P[F[i].b],P[F[i].c],a);
_min=min(_min,now);
}
return _min;
}
double ptoface(pt p,int i)
{
return fabs(volume(P[F[i].a],P[F[i].b],P[F[i].c],p)/vlen((P[F[i].b]-P[F[i].a])*(P[F[i].c]-P[F[i].a])));
}
}lou;
bool mult(pp sp,pp ep,pp op){
return (sp.x-op.x)*(ep.y-op.y)>=(ep.x-op.x)*(sp.y-op.y);
}
double Cross(pp a,pp b,pp c){
return (c.x-a.x)*(b.y-a.y) - (b.x-a.x)*(c.y-a.y);
} bool cmp(pp a,pp b){
if(a.y==b.y)return a.x<b.x;
return a.y<b.y;
}
int n,res[],top;
pp ps[];
void Graham(){
int len;
n=lou.n;
top=;
sort(ps,ps+n,cmp);
if(n==)return;res[]=;
if(n==)return;res[]=;
if(n==)return;res[]=;
for(int i=;i<n;i++){
while(top&&mult(ps[i],ps[res[top]],ps[res[top-]]))
top--;
res[++top]=i;
}
len=top;
res[++top]=n-;
for(int i=n-;i>=;i--){
while(top!=len&&mult(ps[i],ps[res[top]],ps[res[top-]]))top--;
res[++top]=i;
}
}
inline pt get_point(pt st,pt ed,pt tp)
{
double t1=(tp-st)^(ed-st);
double t2=(ed-st)^(ed-st);
double t=t1/t2;
pt ans=st + ((ed-st)*t);
return ans;
}
inline double dist(pt st,pt ed)
{
return sqrt((ed-st)^(ed-st));
}
pp rotate(pt st,pt ed,pt tp,double A)
{
pt root=get_point(st,ed,tp);
pt e=(ed-st)/dist(ed,st);
pt r=tp-root;
pt vec=e*r;
pt ans=r*cos(A)+vec*sin(A)+root;
return pp(ans.x,ans.y);
}
int main(){
while (scanf("%d",&lou.n)&&lou.n) {
for (int i=; i<lou.n; ++i)
scanf("%lf%lf%lf",&lou.P[i].x,&lou.P[i].y,&lou.P[i].z);
lou.construct();
double ansh=,ansa=inf;
if(lou.n<=)
{
printf("0.000 0.000\n");
}
else if(lou.n==)
{
ansh=;
ansa=(lou.P[]-lou.P[])^(lou.P[]-lou.P[]);
ansa/=2.0;
printf("%.3lf %.3lf\n",ansh,ansa); }
else {
for (int i=; i<lou.cnt; ++i) {
pt p1=(lou.P[lou.F[i].b]-lou.P[lou.F[i].a])*(lou.P[lou.F[i].c]-lou.P[lou.F[i].a]);
pt e=pt(,,);
pt vec=p1*e;
double A=p1^e/p1.len();
A=acos(A);
if(fabs(A-pi)>EPS&&fabs(A)>EPS){
pt s=pt(,,);
for (int k=; k<lou.n; ++k) ps[k]=rotate(s,vec,lou.P[k],A);
}
else
{
for(int k=; k<lou.n; ++k) ps[k].x=lou.P[k].x,ps[k].y=lou.P[k].y;
}
double h=;
for (int j=; j<lou.n; ++j)
h=max(lou.ptoface(lou.P[j],i),h);
if (h<ansh)
continue;
Graham();
double a=;
for (int k=; k<top-; ++k){
a+=fabs(Cross(ps[res[]],ps[res[k]],ps[res[k+]]));
}
a/=2.0;
if (fabs(h-ansh)<EPS) {
ansa=min(ansa,a);
}
else
ansa=a;
ansh=h;
}
printf("%.3lf %.3lf\n",ansh,ansa);
}
}
}
Problem I
签到题，就是计算所有数的平方和
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
ll n;
int main()
{
while (~scanf("%lld",&n))
{
if (n==) break;
ll sum=;
while (n--)
{
ll x;
scanf("%lld",&x);
sum+=x*x;
}
printf("%lld\n",sum);
}
return ;
}
Problem J
由于只有裤子跟衣服或鞋子搭配不合法
因此可以求出每条裤子跟多少衣服和鞋子搭配是合法的
然后用乘法原理进行统计即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
int n,m,k,sum1[],sum2[];
char s1[],s2[];
int main()
{
while (~scanf("%d%d%d",&n,&m,&k))
{
if (n==&&m==&&k==) break;
int q;
int i;
for (i=;i<=m;i++)
{
sum1[i]=n;
sum2[i]=k;
}
scanf("%d",&q);
while (q--)
{
int x,y;
scanf("%s%d%s%d",s1,&x,s2,&y);
if (s1[]=='c') sum1[y]--;
else sum2[x]--;
}
ll ans=;
for (i=;i<=m;i++)
ans+=1ll*sum1[i]*sum2[i];
printf("%lld\n",ans);
}
return ;
}
Problem K
根据题意进行模拟即可
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define y1 dfggf
#define y2 kkljk
const int d[][]={{,},{,},{,-},{-,}};
int c1,s1,t1,c2,s2,t2,n,t;
int main()
{
while (~scanf("%d",&n))
{
if (n==) break;
char c[];
scanf("%s%d%d",c,&s1,&t1);
if (c[]=='E') c1=;
else if (c[]=='S') c1=;
else if (c[]=='W') c1=;
else c1=;
scanf("%s%d%d",c,&s2,&t2);
if (c[]=='E') c2=;
else if (c[]=='S') c2=;
else if (c[]=='W') c2=;
else c2=;
scanf("%d",&t);
int i;
int x1=,y1=,x2=n,y2=n;
for (i=;i<=t;i++)
{
int nx1=x1+d[c1][]*s1;
int ny1=y1+d[c1][]*s1;
if (nx1<)
{
nx1=+(-nx1);
c1=;
}
if (nx1>n)
{
nx1=n-(nx1-n);
c1=;
}
if (ny1<)
{
ny1=+(-ny1);
c1=;
}
if (ny1>n)
{
ny1=n-(ny1-n);
c1=;
}
int nx2=x2+d[c2][]*s2;
int ny2=y2+d[c2][]*s2;
if (nx2<)
{
nx2=+(-nx2);
c2=;
}
if (nx2>n)
{
nx2=n-(nx2-n);
c2=;
}
if (ny2<)
{
ny2=+(-ny2);
c2=;
}
if (ny2>n)
{
ny2=n-(ny2-n);
c2=;
}
if (nx1==nx2&&ny1==ny2)
swap(c1,c2);
else
{
if (i%t1==)
{
c1--;
if (c1==-) c1=;
}
if (i%t2==)
{
//cout<<c2<<" ";
c2--;
//cout<<i<<" "<<c2<<endl;
if (c2==-) c2=;
}
}
x1=nx1;
y1=ny1;
x2=nx2;
y2=ny2;
//cout<<i<<endl;
//cout<<x1<<" "<<y1<<" "<<c1<<endl;
//cout<<x2<<" "<<y2<<" "<<c2<<endl;
}
printf("%d %d\n",x1,y1);
printf("%d %d\n",x2,y2);
}
return ;
}
