SGU 297
题意：就是求余数
收获：无
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int main(){ int n,m; scanf("%d%d",&n,&m); int sum=0,x; rep(i,0,m) scanf("%d",&x),sum+=x; printf("%d ",sum%n); return 0; }
SGU 152
题意：求每个数占这些数总和的百分比*100，不是整数的可以向上或者向下取整，然后要求最后百分比和为100
收获：先全部非整数的向下取整，然后不够的就从这些非整的+1最后凑出100
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e4+6; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int a[maxn]; bool fg[maxn]; int main(){ int n,sum=0,cnt=0; scanf("%d",&n); int h = 100; rep(i,0,n) scanf("%d",&a[i]),sum+=a[i]; mt(fg,false); rep(i,0,n){ if(100.0*a[i]/sum!=100*a[i]/sum) fg[i] = true; h-=100*a[i]/sum; } rep(i,0,n){ // de(fg[i]) if(fg[i]){ if(h) printf("%d%c",100*a[i]/sum+1," "[i+1==n]),h--; else printf("%d%c",100*a[i]/sum," "[i+1==n]); }else { printf("%d%c",100*a[i]/sum," "[i+1==n]); } } return 0; }
SGU 124
题意：求一个点和一个简单多边形的关系，在边界，在外面，在内部
收获：dfs组成简单多边形，然后多边形和点关系的模板
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int N = 1e4+6; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int tot = 1,cnt = 0; struct P { double x,y; P() {} P(double x, double y) { this->x = x; this->y = y; } P operator + (const P &c) const { return P(x + c.x, y + c.y); } P operator - (const P &c) const { return P(x - c.x, y - c.y); } P operator * (const db &c) const { return P(x * c, y * c); } P operator / (const db &c) const { return P(x / c, y / c); } }; bool vis[N]; P p[N]; db x(P a){ return a.x; } db y(P a){ return a.y; } void print(P p) { printf("%lf %lf ",p.x,p.y); } int sign(double x) { return (x>eps)-(x<-eps); } db dot(P a, P b) { return x(a) * x(b) + y(a) * y(b); } double cross(P a, P b) { return x(a) * y(b) - x(b) * y(a); } //判断线段是否规范相交（交点不在任一个端点上） bool isSS0(P a1, P a2, P b1, P b2) { double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1), c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1); return sign(c1) * sign(c2) < 0 && sign(c3) * sign(c4) < 0; } //判断线段是否不规范相交 bool isSS1(P a1, P a2, P b1, P b2) { double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1), c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1); return sign(max(x(a1), x(a2)) - min(x(b1), x(b2))) >= 0 && sign(max(x(b1), x(b2)) - min(x(a1), x(a2))) >= 0 && sign(max(y(a1), y(a2)) - min(y(b1), y(b2))) >= 0 && sign(max(y(b1), y(b2)) - min(y(a1), y(a2))) >= 0 && sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0; } //判断点是否在线段上（不包括端点） bool onS0(P p, P a, P b) { return sign(cross(p - a, b - a)) == 0 && sign(dot(p - a, p - b)) < 0; } //判断点是否在线段上（包括端点） bool onS1(P p, P a, P b) { return sign(cross(p - a, b - a)) == 0 && sign(dot(p - a, p - b)) <= 0; } //判断点和多边形关系 边上-1 外0 内1 int Pinploy(P o, P *p, int n) { int res = 0; rep(i, 0, n) { P u = p[i], v = p[(i + 1) % n]; if(onS1(o, u, v)) return -1; int k = sign(cross(v - u, o - u)); int d1 = sign(y(u) - y(o)); int d2 = sign(y(v) - y(o)); if(k > 0 && d1 <= 0 && d2 > 0) ++res; if(k < 0 && d2 <= 0 && d1 > 0) --res; } return res != 0; } map<pii,int> m; map<int,pii> mm; vector<int> G[N]; int id(pii a){ if(m.count(a)) return m[a]; else m[a]=(tot++); mm[tot-1] = a; return m[a]; } void add(int u,int v){ G[u].pb(v),G[v].pb(u); } void dfs(int u){ vis[u]=true; p[cnt++]=P(mm[u].fi,mm[u].se); rep(i,0,sz(G[u])){ int v=G[u][i]; if(vis[v]) continue; dfs(v); } } int main(){ int n,xx,yy; scanf("%d",&n); rep(i,0,n){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); int t = id(mp(a,b)); int tt = id(mp(c,d)); add(t,tt); } dfs(1); // de(cnt) scanf("%d%d",&xx,&yy); P pp = P(xx,yy); int ans = Pinploy(pp,p,cnt); if(ans==1) puts("INSIDE"); if(ans==0) puts("OUTSIDE"); if(ans==-1) puts("BORDER"); return 0; }