头像

溪染




离线:3个月前


最近来访(40)
用户头像
阿吉迷得牛炖咖喱略
用户头像
赤旗
用户头像
Struggling-Survivor
用户头像
Iuao
用户头像
Tkybk_dz
用户头像
Wuko
用户头像
Misaka_9982
用户头像
zqsz
用户头像
OverHealth
用户头像
MySoulJuly
用户头像
陶晰睿
用户头像
种花家的小兔子
用户头像
铃兰の顶点
用户头像
zombotany
用户头像
zoler
用户头像
lyuacm
用户头像
一个弱鸡
用户头像
Acckno1
用户头像
qwewngybdfgc
用户头像
董洞洞同学

新鲜事 原文

溪染
7个月前
WC考完了 颓废开始了 [颓废入口](http://tool.liumingye.cn/music/?page=audioPage&type=YQD&name=%E6%98%9F%E6%98%9F%E5%9C%A8%E5%94%B1%E6%AD%8C%20-%20%E5%8F%B8%E5%8D%97%2FCMJ%2FMango%20Daddy)



溪染
8个月前
#include<bits/stdc++.h>
using namespace std;
const int N=4e6+7;
struct oppo{
    int to,nex;
}rod[N];
int head[N],tot;
void add(int from,int to)
{
    rod[++tot].to=to;
    rod[tot].nex=head[from];
    head[from]=tot;
}
int n,m;
int dfn[N],low[N],all;
int in[N];
int stk[N],hh;
int clo[N],clo_tot;
void dfs(int x)
{
    dfn[x]=low[x]=++all;
    stk[++hh]=x;in[x]=1;
    for(int i=head[x];i;i=rod[i].nex){
        int to=rod[i].to;
        if(!dfn[to]){
            dfs(to);
            low[x]=min(low[to],low[x]);
        }else if(dfn[to]&&in[to])
            low[x]=min(low[x],dfn[to]);
    }
    if(low[x]==dfn[x]){
        ++clo_tot;
        while(stk[hh+1]!=x){
            clo[stk[hh]]=clo_tot;
            in[stk[hh]]=0;
            hh--;
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,a,y,b;
        scanf("%d%d%d%d",&x,&a,&y,&b);
        x*=2;y*=2;
        add(x|(!a),y|b);//若xa不选,yb必选
        add(y|(!b),x|a);//若yb不选,xa必选
    }
    for(int i=2;i<=2*n+1;i++)
        if(!dfn[i])
            dfs(i);
    for(int i=1;i<=n;i++)
        if(clo[i*2]==clo[i*2+1]){
            puts("IMPOSSIBLE");
            return 0;
        }
    puts("POSSIBLE");
    for(int i=1;i<=n;i++)
        cout<<(clo[i*2]>clo[i*2+1])<<" ";
    return 0;
}


新鲜事 原文

溪染
8个月前
计算几何66行的代码,我愣是调了4个小时 哭了:(



溪染
8个月前
#include<bits/stdc++.h>
using namespace std;
struct point{
    double x,y;
    point(){};
    point(double x,double y):x(x),y(y){};
    point operator-(point b){return point(x-b.x,y-b.y);}
    point operator+(point b){return point(x+b.x,y+b.y);}
    point operator*(double b){return point(x*b,y*b);}
    double operator%(point b){return x*b.y-y*b.x;}
}d[1010];
struct line{
    point st,ed;
    double get_slope(){return atan2((ed-st).y,(ed-st).x);}
    bool operator<(line b){
        double a=this->get_slope();
        double c=b.get_slope();
        if(fabs(a-c)>1e-8)
            return a<c;
        return (b.st-st)%(b.ed-st)>0;
    }
}p[1010];
point get_intersection(line s,line t){
    double k=((t.ed-t.st)%(s.st-t.st))/((s.ed-s.st)%(t.ed-t.st));
    return s.st+(s.ed-s.st)*k;
}
bool is_right(point a,line b){
    return (a-b.st)%(b.ed-b.st)>=0;
}
int cnt,n,stk[1010],hh=-1,tt;
double work(){
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        if(i!=1&&fabs(p[i].get_slope()-p[i-1].get_slope())<1e-8) continue;
        while(tt+1<=hh && is_right(get_intersection(p[stk[hh]],p[stk[hh-1]]),p[i])) hh--;
        while(tt+1<=hh && is_right(get_intersection(p[stk[tt]],p[stk[tt+1]]),p[i])) tt++;
        stk[++hh]=i;
    }
    while(tt+1<=hh && is_right(get_intersection(p[stk[hh]],p[stk[hh-1]]),p[stk[tt]])) hh--;
    while(tt+1<=hh && is_right(get_intersection(p[stk[tt]],p[stk[tt+1]]),p[stk[hh]])) tt++;
    stk[++hh]=stk[tt];
    int k=0;
    for(int i=tt;i<hh;i++)
        d[++k] = get_intersection(p[stk[i]],p[stk[i+1]]);
    double res=0;
    for(int i=1;i<=k;i++)
        res+=d[i]%d[i%k+1];
    return fabs(res/2);
}
int main(){
    cin>>cnt;
    for(int i=1;i<=cnt;i++){
        int m;
        scanf("%d",&m);
        for(int j=0;j<m;j++)
            scanf("%lf%lf",&d[j].x,&d[j].y);
        for(int j=0;j<m;j++){
            p[++n].st=d[j];
            p[n].ed=d[(j+1)%m];
        }
    }
    double ans=work();
    ans= ans==ans?ans:0;
    printf("%.3lf",ans);
    return 0;
}



溪染
8个月前
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
struct point{
    double x,y;
    point(){};
    point(double x,double y):x(x),y(y){};
    double operator%(point b){
        return x*b.y-y*b.x;
    }
    point operator-(point b){
        return point(x-b.x,y-b.y);
    }
    point operator+(point b){
        return point(x+b.x,y+b.y);
    }
    point rotate(double s){
        return point(x*cos(s)-y*sin(s),y*cos(s)+x*sin(s));
    }
    bool operator<(point b){
        return x<b.x;
    }
}p[40010];
double distanc(point a,point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
int n;
double a,b,r;
int stk[40010];
bool uers[40010];
double work()
{
    int tp=0;
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]]) % (p[i]-p[stk[tp-1]]))>=0)
            uers[stk[tp--]]=0;
        uers[i]=1;
        stk[++tp]=i;
    }
    uers[1]=0;
    for(int i=n;i>=1;i--){
        if(uers[i]) continue;
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]]) % (p[i]-p[stk[tp-1]]))>=0)
            tp--;
        stk[++tp]=i;
    }
    double ans=0;
    for(int i=2;i<=tp;i++)
        ans+=distanc(p[stk[i]],p[stk[i-1]]);
    return ans;
}
int main()
{
    cin>>n;
    cin>>b>>a>>r;
    for(int i=1;i<=n;i++){
        double x,y,s;
        scanf("%lf%lf%lf",&x,&y,&s);
        point st=point(x,y);
        p[4*i-3]=st+point(a/2-r,b/2-r).rotate(s);
        p[4*i-2]=st+point(-a/2+r,b/2-r).rotate(s);
        p[4*i-1]=st+point(a/2-r,-b/2+r).rotate(s);
        p[4*i-0]=st+point(-a/2+r,-b/2+r).rotate(s);
    }
    n=4*n;
    printf("%.2lf",work()+acos(-1)*r*2);
    return 0;
}



溪染
8个月前

当你把长和宽读反了
但是你可以获得80分的好成绩
(不要问我怎么知道有80分)




溪染
8个月前
#include<bits/stdc++.h>
using namespace std;
struct Point{
    double x,y;
    Point(){};
    Point(double x,double y):x(x),y(y){};
    Point operator-(Point b){
        return Point(x-b.x,y-b.y);
    }
    double operator%(Point b){
        return x*b.y-y*b.x;//叉乘 
    }
    bool operator<(Point b){
        return x<b.x;
    }
}p[10005];
int n;
int stk[10005];
bool uers[10005];
double distanc(Point a,Point b)
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
double work()//求凸包  
{
    int tp=0;
    for(int i=1;i<=n;i++){
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]])%(p[i]-p[stk[tp-1]]))>0)
            uers[stk[tp--]]=0;
        uers[i]=1;
        stk[++tp]=i;
    }
    uers[1]=0;
    for(int i=n;i>=1;i--){
        if(uers[i]) continue;
        while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]])%(p[i]-p[stk[tp-1]]))>0)
            tp--;
        stk[++tp]=i;
    }
    double ans=0;
    for(int i=2;i<=tp;i++)
        ans+=distanc(p[stk[i]],p[stk[i-1]]);
    return ans;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        double x,y;
        scanf("%lf%lf",&x,&y);
        p[i]=Point(x,y);
    }
    sort(p+1,p+n+1);
    printf("%.2lf",work());
    return 0;
}



溪染
8个月前

定义了点,向量的结构体,重载运算符
二分判断即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct oppo{
    int x,y;
    oppo(){};
    oppo(int x,int y):x(x),y(y){};
    oppo operator -(){
        return oppo(-x,-y);
    }
    oppo operator -(oppo b){
        return oppo(x-b.x,y-b.y);
    }
    oppo operator +(oppo b){
        return oppo(x+b.x,y+b.y);
    }
    oppo operator *(int b){
        return oppo(x*b,y*b);
    }
    int operator *(oppo b){
        return x*b.x+y*b.y;//点乘 
    }
    int operator ^(oppo b){
        return x*b.y-y*b.x;//叉乘 
    }
    oppo operator /(int b){
        return oppo(x/b,y/b);
    }
    void out(){
        printf("(%lld,%lld)\n",x,y);
    }
}p[10000][3];
int tot[10000];
int n,m,x,y,xx,yy; 
void find(oppo k)
{
    int l=1,r=n,mid,ans=0;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(((k-p[mid][0])^(p[mid][1]-p[mid][0]))>=0){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    tot[ans]++;
}
int T;
signed main()
{
    while(++T)
    {
        scanf("%lld",&n);if(!n) break;
        if(T!=1) puts("");
        scanf("%lld%lld%lld%lld%lld",&m,&x,&y,&xx,&yy);
        memset(tot,0,sizeof(tot));
        for(int i=1;i<=n;i++){
            int a,b;
            scanf("%lld%lld",&a,&b);
            p[i][1]=oppo(a,y);
            p[i][0]=oppo(b,yy);
        }
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%lld%lld",&a,&b);
            find(oppo(a,b));
        }
        for(int i=0;i<=n;i++)
            printf("%lld: %lld\n",i,tot[i]);
    }
    return 0;
}



溪染
8个月前

gethub地址: https://github.com/forthespada/CS-Books
预览(还有一部分没有截图上来):
QQ截图20210120082418.png



问题 测评环境

溪染
8个月前

ACwing的测评是在windows环境下测评的吗?